Задача 445
Втягивания А

Для каждого целого n>1, семья функций fn,a,b задана как fn,a,b(x)≡ax+b mod n для целых a,b,x и 0x Назовем fn,a,b втягиванием, если fn,a,b(fn,a,b(x))≡fn,a,b(x) mod n для каждого 0≤x Пусть R(n) будет количеством втягиваний для n.

Вам дано, что
R(c) для c=C(100 000,k), и 1 ≤ k ≤99 999 ≡628701600 (mod 1 000 000 007).
(C(n,k) - биномиальный коэффициент).

Найдите R(c) для c=C(10 000 000,k), и 1 ≤k≤ 9 999 999.
В качестве ответа приведите остаток деления полученного числа на 1 000 000 007.

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