题目大意：给你一个数字 n ，n 个数字能分成多少组分类情况。

思路：这题要用插空法，一共 n 个数字，所以一共有 n - 1 个空可以插入，所以这道题目的答案就是，由二项式定理易得这个式子的和为 。但是输入的这个 n 可能会很大（需要字符串输入），导致这个指数会特别大，所以我们要用费马小定理（%p=1）来降幂。

二项式推导求和：

=

当 x=y=1 时，

费马小定理（%p=1）降幂:

%p=1 ,  即当指数是模数-1的时候值为 1 ，所以我们可以把  转化一下 

             无论 n 为何值 ，都有 m * ( p - 1) + k = n ，m 和 k 都为整数

        由费马小定理易得  % p = 1

 

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int ksm(int x,int y){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return ans;
}
signed main(){
	string s;
	while(cin >> s){
		int ans=0;
		for(int i=0;i<s.size();i++){//用费马小定理降幂 
			ans=(ans*10+s[i]-'0')%(mod-1);
		}
		ans=(ans-1+mod-1)%(mod-1);//保证指数非负 
		cout << ksm(2,ans) << endl;
	}
    return 0;
}