原题在此
题目先假设了这样一个函数s(k,n)，其作用是把n分解成k个正数之和，分法的种类。然后问，\sum_{i=1}^{n}{s(i,n)}.

拿到题目，首先考虑了四种特殊情况：k=1、2、n、n-1.很明显，结果应该是1、n-1、1、n-1.于是猜测，应该是组合数。

然后证明。假设有n个小球，按顺序排列，在空隙中插入k-1块板子，这就得到了一种分割。确实是组合数。

那么组合数的和就很方便了，是2^{n-1}.

但是一看数据范围，吓了一跳，1 \leq n \leq 10^{100000}.即使快速幂也一定会TLE。当时的我就这样败下阵来。

但是，这时候轮到费马小定理出场了，a^{p-1}≡1(\mod p),题目要求模1e9+7，于是原式加速为2^{(n-1)\mod {(p-1)}} \mod p。是极大的飞跃，但是十万位的n还是难以取模。

假设n从左往右数第i位是a[i],到第i为为止的n是n[i],可以得到这样一个式子：n[i] \mod p = (n[i-1]*10 \mod p +a[i])\mod p;递推下去，把n读完即可。

由于我并没有a这一题，所以这一题就不放代码了。