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

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