题意：
这题意看了很久。。
s（k）表示的是把n分成k个正整数的和，有多少种分法。
例如：
n=4时，
s（1）=1 4
s（2）=3 1，3 3，1 2，2
s（3）=3 1，1，2 1，2，1 2，1，1
s（4）=1 1，1，1，1
s（1）+s（2）+s（3）+s（4）=1+3+3+1=8
当n=1，2，3，4时，可以分别求出结果为 1，2，4，8
于是推出答案就是2^(n-1)---------------------（为什么？我也不知道，这个是怎么推出来的）
思路：题意明白了，就是求2^(n-1) mod（10^9+7）呗。
由于这里的n非常大，1<=n<10^100000，这里用简单的暴力绝对超时啊（10^8就会超时）
那么，这里用了两个优化，一个是费马小定理 a^(p-1)≡1(mod p)，另外就是快速幂加速求幂
这里稍微演示一下如何利用费马小定理处理：
（单单用费马小定理处理仍会超时，因为处理完后，指数最大能达到10^9级别，仍会超时）
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1e9+7; void pow(__int64 b){//快速求幂（位操作）
__int64 a=2;
__int64 ans;
ans=1;
while(b>0){
if(b&1)//判断是否为奇数，相当于 if(b%2==1)
ans=(ans*a)%mod;
a=(a*a)%mod;
b=b>>1;//二进制向右移一位，相当于 b=b/2;
}
printf("%I64d\n",ans);
} int main(){
char str[123456];
__int64 num,i;
while(~scanf("%s",str)){
num=0;
int len=strlen(str);
for(i=0;i<len;i++){
num=( num*10+(str[i]-'0') )% (mod-1);//精华部分
}
if(num==0) pow(mod-2);//此时n=mod-1,所以应该求pow(mod-2),而不能求成pow(num-1)
else pow(num-1);
}
return 0;
}