http://codeforces.com/problemset/problem/300/C

 

​

 

长度为n的数字每一位只含a和b，那么这个数字是好的，如果这个数字的每一位加起来的和是一个好的数字，那么该数字被称为极好的。

总共n位，假设数字有x位a，那么要有（n-x）位b，才是好的数字，然后算出来和，如果每一位都是a，b，那么答案加上C(n,x).

x∈[0,n].

 

 

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

ll a,b,n,ans;
ll c[1000000+10];

ll pow_mod(ll a,ll n,ll m)
{
	if(n==0)return 1;
	ll x=pow_mod(a,n/2,m);
	x=x*x%mod;
	if(n&1)x=x*a%mod;
	return x;
}

void init()
{
	c[0]=1;
	for(int i=1;i<=n;i++)c[i]=c[i-1]*(n-i+1)%mod*pow_mod(i,mod-2,mod)%mod;
}

int main()
{
	cin>>a>>b>>n;
	init();
	for(int x=0;x<=n;x++)
	{
		ll num=a*x+(n-x)*b;
		bool ok=1;
		for(;num;num/=10)if(num%10!=a&&num%10!=b)ok=0;
		if(ok)ans=(ans+c[x])%mod; 
	} 
	cout<<ans<<endl;
	return 0;
}