Интересная задача на поиск натуральных делителей бинома

[Laguna]

Здравствуйте, господа, недавно столкнулся со следующей задачей: "На вход подаются 2 числа $n$ и $k$. На выходе необходимо выдать количество НАТУРАЛЬНЫХ делителей биномиального коэффициента $\binom{n}{k}$ по модулю 1000000007"
1 $\leqslant$ $k$ $\leqslant$ $n$ $\leqslant$ 500000
Понятно, что в лоб здесь не получится идти, потому что для некоторых значений $k$ и $n$ число получится огромным. Нашел вот такое тождество:
$\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}$. Но с ним пока ничего не добился. Был бы рад наводящим соображениям.

[mihaild]

Не надо считать биномиальные коэффициенты в явном виде, посмотрите, как выглядит их разложение на простые (и как посчитать число делителей, зная разложение на простые).

[Laguna]

mihaild в сообщении #1633711 писал(а):

Не надо считать биномиальные коэффициенты в явном виде, посмотрите, как выглядит их разложение на простые (и как посчитать число делителей, зная разложение на простые).

Я знаю, как найти количество делителей, зная разложение числа на простые множители, однако, как можно быстро найти разложение биномиального коэффициента на простые множители?

[mihaild]

Laguna в сообщении #1633716 писал(а):

однако, как можно быстро найти разложение биномиального коэффициента на простые множители

Можете ли Вы посчитать, в какой степени число $7$ входит в разложение на простые числа $100!$?

[mathpath]

mihaild в сообщении #1633722 писал(а):

Laguna в сообщении #1633716 писал(а):

однако, как можно быстро найти разложение биномиального коэффициента на простые множители

Можете ли Вы посчитать, в какой степени число $7$ входит в разложение на простые числа $100!$?

100/7=14

[GAA]

mathpath в сообщении #1633853 писал(а):

100/7=14

Legendre's formula:
$\lfloor \frac {100} 7 \rfloor + \lfloor \frac {100} {7^2} \rfloor = 16$.

[mihaild]

mathpath в сообщении #1633853 писал(а):

100/7=14

Нет, это число сомножителей, делящихся на $7$, а не степень, в которой $7$ входит в произведение.
После исправления подумайте, как из этого получить, в какой степени простое число входит в биномиальный коэффициент.