题意
给定整数(q,n(1leq q,nleq 10^9))，求(q^{sum_{d|n}C_{n}^{d}}mod 999911659)
思路
首先由扩展欧拉定理可知，因为999911659为质数
[q^{sum_{d|n}C_{n}^{d}}equiv q^{sum_{d|n}C_{n}^{d} mod 999911658}mod 999911659
]
设(x=sum_{d|n}C_{n}^{d} mod 999911658)，然后再 由于(fact(999911658)=2*3*4679*35617)，所以可以先以2,3,4679,35617为模数求(sum_{d|n}C_{n}^{d})，分别记作(a_1,a_2,a_3,a_4)，那么求解以下方程组即可得到(x)
[egin{cases} xequiv a_1 mod 2\ xequiv a_2 mod 3 \ xequiv a_3 mod 4679 \ xequiv a_4 mod 35617end{cases}
]
无足轻重的解释：(p_i|x-a_i)，那么满足这些情况的(x)一定满足其积
然后再求(q^xmod 999911659)即可