2

2

Hint

1.  For N = 2, S(1) = S(2) = 1.

2.  The input file consists of multiple test cases. 

好难理解的题意。

S(1)是代表把数字N分解为1个数，S(2)代表把N分解为2个数，S(3)代表把N分解为3个数。

其和都不等于N。

最后问把S(1) + S(2) + .. S(N)加起来的和有多少个？

就是个计数的问题。

最后得到公式这种和有2^(N-1)个。

最后问题转化为求大数2^(N-1) % 1E9 + 7的一个高幂次数求余问题。

參考了下这个博客：http://blog.csdn.net/xingyeyongheng/article/details/10910543

数学思维好抽象的。

const int SIZE = 100001;

const int MOD = int(1E9 + 7);

char nums[SIZE];

__int64 Fermat(char *n, int mod)

{

	__int64 ans = 0;

	for (int i = 0; n[i]; i++)

	{

		ans = (ans * 10L + n[i] - '0') % mod;

	}

	return ans;

}

__int64 fastPow(__int64 base, __int64 p)

{

	p = (p + MOD) % MOD;

	__int64 ans = 1;

	while (p)

	{

		if (p & 1) ans = ans * base % MOD;

		base = base * base % MOD;

		p >>= 1;

	}

	return ans;

}

int main()

{

	while(gets(nums) != NULL)//scanf("%s", nums) != EOF)

	{

		__int64 n = Fermat(nums, MOD-1) - 1;

		printf("%I64d\n",fastPow(2, n));

	}

	return 0;

}