[2018icpc Jiaozuo Network Game Save the Room] [Combination Number [Separator Method] [High Power Power Module]

[Link]

[题意与思维]

Split a Number The number of methods and the number of methods.

如4=1+1+1+1=1+1+2=2+2=1+3=4

Equivalent to (n-1) empty inserts, number of methods That is 2^(n-1).

[code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1000005;
const ll mod = 1000000007LL;
char s[maxn];
ll qpow(ll a, ll n) {
	ll res = 1;
	while (n > 0)
	{
		if (n & 1)
			res = res * a  % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int main() {
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%s", s);
		ll ans = 1;
		int l = strlen(s);
		for (int i = 0; i < l; ++i) {
			int n = s[i] - '0';
			ans = qpow(ans, 10) * qpow(2, n);
			ans %= mod;
		}
		ans = ans * qpow(2, mod - 2) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}