Задача 495
Запись n в виде произведения k различных положительных целых чисел

Пусть W(n,k) будет количеством способов, которыми можно записать число n в виде произведения k различных положительных целых чисел.

Например, W(144,4) = 7. Существует 7 способов, которыми число 144 можно записать в виде произведения 4 различных положительных целых чисел:

  • 144 = 1×2×4×18
  • 144 = 1×2×8×9
  • 144 = 1×2×3×24
  • 144 = 1×2×6×12
  • 144 = 1×3×4×12
  • 144 = 1×3×6×8
  • 144 = 2×3×4×6

Заметьте, что перестановки одних и тех же множителей не считаются различными способами записи.

Также W(100!,10) modulo 1 000 000 007 = 287549200.

Найдите W(10000!,30) modulo 1 000 000 007.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net