令 $$f_{n,a,b}(x)=ax+b \pmod n,$$ 其中$a,b,x\in\mathbb Z$且$0 < a < n, 0\le b < n, 0\le x < n$。若 $$f_{n,a,b}(f_{n,a,b}(x))=f_{n,a,b}(x) \pmod n,$$ 对任意$0\le x < n$都成立，就称$f_{n,a,b}$为收缩函数。

记$R(n)$是n所对应的收缩函数的总数，可以验证 $$\sum_{k=1}^{99999}R(\binom{100000}{k})=628701600 \pmod {10^9+7}.$$ 求$\sum_{k=1}^{10^7-1}R(\binom{10^7}{k})$模$10^9+7$的余数。

本题难度:

解答

根据题意有 $$a(ax+b)+b=ax+b \pmod n.$$ 即 $$(a^2-a)x+ab=0 \pmod n.$$ 取$x=0$有ab能被n整除，再取$x=1$可得$a^2-a=a(a-1)$也能被n整除。

设n的质因数分解是$n=p_1^{e_1}\ldots p_m^{e_m}$，对任意一个素幂因子$p_k^{e_k}$，由于$\gcd(a,a-1)=1$，因此或者$p_k^{e_k}|a$，此时b可以取任意值，或者$p_k^{e_k}|a-1$，此时b需要也是$p_k^{e_k}$的倍数。

把以上关系放在$\mathbb Z_{p_k^{e_k}}$中计数，再结合a不为0的条件就可得 $$R(n)=\prod_{k=1}^m(p_k^{e_k}+1)-n.$$ 本题中的n是组合数$\binom{N}{k}$的形式，利用$\binom{N}{k}=\frac{N-k+1}{k}\cdot\binom{N}{k-1}$递推计算其质因数分解以及$\sum_{k=0}^N\binom{N}{k}=2^N$即可得结果$659104042$。

注：因需要内建函数作快速幂，以下代码为Python 3，代码中还打印了进度信息。

import sympy,math

target=10**15

n,g=4,13
while True:
    d=min((g+p-1)//p*p for p in sympy.primefactors(g-n-1))
    m=n+d-g+1
    if m>target:
        g+=target-n
        break
    g=d+math.gcd(m,d)
    n=m

print(g)