26. Лето у бабушки

В прекрасную солнечную Кубань приехали на лето к бабушке брат и сестра Пафнутий и Алевтина. Пафнутий и Алевтина каждый день летних каникул играли с кубиками и больше всего им понравилась следующая игра:

Есть два игрока, игроки по очереди бросают по одному $k$-гранному кубику, пока число выпавших кубиков не будет равно $m$. Когда выпало $m$ кубиков, игроки перемножают выпавшие на кубиках числа и считают количество делителей и у получившегося числа. Если это число имеет нечетное число делителей, то победил первый игрок. В обратном случае побеждает второй игрок.

Пафнутий начинает первым. А Пафнутий очень любознательный мальчик, поэтому он просит вас ответить ему на один единственный вопрос: какая вероятность его победы, если все кубики бросаются независимо?

Можно показать, что ответ может быть представлен в виде несократимой дроби $\frac{p}{q}$, где $p$ и $q$ ~--- целые числа, и $q \not \equiv 0 \pmod{1\,000\,000\,007}$. Выведите целое число, равное $p \cdot q^{-1} \bmod 1\,000\,000\,007$. Другими словами, выведите такое целое число $x$, что $0 \le x < 1\,000\,000\,007$ и $x \cdot q \equiv p \pmod{1\,000\,000\,007}$.

В первой и единственной строке находятся два целых числа $-$ число кубиков $1 \le m \le 1000$, число граней каждого кубика $3 \le k \le 20$

Выведите одно целое число $-$ значение $p \cdot q^{-1} \bmod 1\,000\,000\,007$

Кубик называется $k$ гранным если на его гранях записаны цифры от 1 до $k$ и все они могут равновероятно выпасть на кубике.