Vitaly is a very weird man. He's got two favorite digits a and b. Vitaly calls a positive integer good, if the decimal representation of this integer only contains digits a and b. Vitaly calls a good number excellent, if the sum of its digits is a good number.

For example, let's say that Vitaly's favourite digits are 1 and 3, then number 12 isn't good and numbers 13 or 311 are. Also, number 111 is excellent and number 11 isn't. 

Now Vitaly is wondering, how many excellent numbers of length exactly n are there. As this number can be rather large, he asks you to count the remainder after dividing it by 1000000007 (10^9 + 7).

A number's length is the number of digits in its decimal representation without leading zeroes.


-----Input-----

The first line contains three integers: a, b, n (1 ≤ a < b ≤ 9, 1 ≤ n ≤ 10^6).


-----Output-----

Print a single integer — the answer to the problem modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
1 3 3

Output
1

Input
2 3 10

Output
165

Difficulty: interview

Starter code:

Solutions:
ans = 0
mod = 1000000007
a, b, n = list(map(int, input().split()))
s = set()
for x in range(2, 1 << 8):
    z = 0
    while x > 1:
        z = z * 10 + (a, b)[x & 1]
        x >>= 1
    s.add(z)
f = [1] * (n + 1)
for i in range(1, n + 1):
    f[i] = f[i - 1] * i % mod
for x in range(n + 1):
    if x * a + (n - x) * b in s:
        ans += pow(f[x] * f[n - x], mod - 2, mod)
        ans %= mod
print(ans * f[n] % mod)


from bisect import bisect_right, bisect_left

a, b, n = map(int, input().split())
if a > b: a, b = b, a

u, v = 10 * a, 10 * b
x, y = a * n, b * n
t, d = [a, b], b - a

while t[-1] < x:
    t = [j + u for j in t] + [j + v for j in t]
    u, v = u * 10, v * 10
if t[-1] < y: t += [j + u for j in t] + [j + v for j in t]

t, s = t[bisect_left(t, x): bisect_right(t, y)], 0
m, f = 1000000007, [1] + [0] * n
p, k = list(range(x, y + 1, d)), 0

for i in range(1, n + 1):
    f[i] = (f[i - 1] * i) % m

for i in t:
    k = bisect_left(p, i)
    if p[k] == i: s += pow(f[k] * f[n - k], m - 2, m)

print(((s % m) * f[n]) % m)

MOD = int( 1e9 + 7 )

fact = [ 1 ]
for i in range( 1, int( 1e6 ) + 1, 1 ):
  fact.append( fact[ i - 1 ] * i % MOD )

A, B, N = list(map( int, input().split() ))

ans = 0
for i in range( N + 1 ):
  f = A * i + B * ( N - i )
  ng = False
  while f:
    t = f % 10
    if t != A and t != B:
      ng = True
      break
    f //= 10
  if ng: continue
  ans = ( ans + fact[ N ] * pow( fact[ i ], MOD - 2, MOD ) * pow( fact[ N - i ], MOD - 2, MOD ) ) % MOD

print( ans )


MOD=10**9+7

a,b,n=list(map(int,input().strip().split(' ')))
#there are i a's. n-i b's
def check(a,b,x):
    temp=x%10
    if temp!=a and temp!=b:
        return 0
    while(x>0):
        temp=x%10
        if temp!=a and temp!=b:
            return 0
        x=x//10
    return 1    

fact=[1]
infact=[1]
temp=1
intemp=1
for i in range(1,n+1):
    temp*=i
    #intemp*=pow(i,MOD-2,MOD)
    temp%=MOD
    #intemp%=MOD
    fact+=[temp]
    #infact+=[intemp]
    
def binom(a,b):
    MOD=10**9+7
    if b==0:
        return 1
    else:
        temp=pow(fact[a-b]*fact[b],MOD-2,MOD)*fact[a]
        return temp%MOD
        
        
        
    
    
total=0    
for i in range(n+1):
    temp=i*a+(n-i)*b
    if check(a,b,temp)==1:
        total+=binom(n,i)
        total%=MOD
#total*=fact[a]        
print(total%MOD)      

from bisect import bisect_right, bisect_left



a, b, n = list(map(int, input().split()))

if a > b: a, b = b, a



u, v = 10 * a, 10 * b

x, y = a * n, b * n

t, d = [a, b], b - a



while t[-1] < x:

    t = [j + u for j in t] + [j + v for j in t]

    u, v = u * 10, v * 10

if t[-1] < y: t += [j + u for j in t] + [j + v for j in t]



t, s = t[bisect_left(t, x): bisect_right(t, y)], 0

m, f = 1000000007, [1] + [0] * n

p, k = list(range(x, y + 1, d)), 0



for i in range(1, n + 1):

    f[i] = (f[i - 1] * i) % m



for i in t:

    k = bisect_left(p, i)

    if p[k] == i: s += pow(f[k] * f[n - k], m - 2, m)



print(((s % m) * f[n]) % m)



# Made By Mostafa_Khaled


a,b,n=list(map(int,input().split()))

def ok(s):
    # print('sum',s)
    while s:
        if s%10!=a and s%10!=b:
            return False
        s=int(s/10)
    # print('ok')
    return True

ans=0
p=int(1e9+7)
A=[1]
for i in range(1,n+1):
    A.append(int(i*A[i-1]%p))
for x in range(0,n+1):
    y=n-x
    # print(a,x,b,y,a*x+b*y)
    if ok(a*x+b*y):
        ans+=(A[n]*pow(A[x],p-2,p))%p*pow(A[y],p-2,p)%p
        ans%=p
    # input()

print(int(ans))


a,b,n=list(map(int,input().split()))

def ok(s):
    # print('sum',s)
    while s:
        if s%10!=a and s%10!=b:
            return False
        s=int(s/10)
    # print('ok')
    return True

ans=0
p=int(1e9+7)
A=[1]
for i in range(1,n+1):
    A.append(int(i*A[i-1]%p))
for x in range(0,n+1):
    y=n-x
    # print(a,x,b,y,a*x+b*y)
    if ok(a*x+b*y):
        ans+=(A[n]*pow(A[x],p-2,p))%p*pow(A[y],p-2,p)%p
        ans%=p
    # input()

print(int(ans))


a,b,n = list(map(int,input().split()))
m =1000000007
fact = [1]

for i in range(1,n+1):
    fact.append((fact[-1]*i)%m)
ans = 0
for i in range(n+1):
    su = (a*i) + b*(n-i)
    coef = 1
    while(su>0):
        if(su%10 != a and su%10!=b):
            coef = 0;
        su//=10
    if coef:
        ans+=(fact[n]*pow((fact[i]*fact[n-i]),m-2,m))
        ans= ans%m
print(ans%m)
    


import sys

inf = float("inf")
# sys.setrecursionlimit(10000000)

# abc='abcdefghijklmnopqrstuvwxyz'
# abd={'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod, MOD = 1000000007, 998244353
# words = {1:'one',2:'two',3:'three',4:'four',5:'five',6:'six',7:'seven',8:'eight',9:'nine',10:'ten',11:'eleven',12:'twelve',13:'thirteen',14:'fourteen',15:'quarter',16:'sixteen',17:'seventeen',18:'eighteen',19:'nineteen',20:'twenty',21:'twenty one',22:'twenty two',23:'twenty three',24:'twenty four',25:'twenty five',26:'twenty six',27:'twenty seven',28:'twenty eight',29:'twenty nine',30:'half'}
# vow=['a','e','i','o','u']
# dx,dy=[0,1,0,-1],[1,0,-1,0]

# import random
# from collections import deque, Counter, OrderedDict,defaultdict
# from heapq import nsmallest, nlargest, heapify,heappop ,heappush, heapreplace
# from math import ceil,floor,log,sqrt,factorial,pi,gcd
# from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right

def get_array(): return list(map(int, sys.stdin.readline().strip().split()))
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()

def is_beautiful(sum):
    if sum==0:
        return 0
    while sum:
        if sum%10!=a:
            if sum%10!=b:
                return 0
        sum//=10
    return 1

def nCr(n,r):
    return (fact[n]*invfact[r]*invfact[n-r])%mod


# precalculating fact and inverse fact array

fact = [0]*(1000005)
invfact = [0]*(1000005)
fact[0] = fact[1] = invfact[0] = invfact[1] = 1
for i in range(1,1000003):
    fact[i] = (fact[i-1]%mod * i%mod)%mod
invfact[1000000] = pow(fact[1000000],mod-2,mod)
for i in range(999999,0,-1):
    invfact[i] = (invfact[i+1]%mod * (i+1)%mod)%mod

a,b,n = get_ints()
if a==b:
    if is_beautiful(a*n):
        print(1)
    else:
        print(0)
ans = 0
for i in range(n+1):
    if is_beautiful(a*i + b*(n-i)):
        ans+=nCr(n,i)
ans %=mod
print(ans)

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m

a, b, n = map(int, input().split())
c = str(a) + str(b)
f, mod, ans = [1], 1000000007, 0
for i in range(1, n + 1):
    f.append(f[-1] * i % mod)
s = a * n
for i in range(n + 1):
    if all(i in c for i in str(s)):
        ans += f[n] * modinv(f[i] * f[n - i], mod) % mod
    s += b - a
print(ans % mod)

MOD=10**9+7
p=1000009
fact=[0]*p 
fact[0]=1 
for i in range(1,p):
    fact[i]=(fact[i-1]*i)%MOD
def MI(a,MOD):
    return pow(a,MOD-2,MOD)
def ncr(n, k,MOD):
    if n==k or k==0:
        return 1 
    if n<k:
        return 0 
    return (fact[n]*MI(fact[k],MOD)%MOD*MI(fact[n-k],MOD)%MOD)%MOD
a,b,n=map(int,input().split())
good=[a,b]
j=-1 
for i in range(10**5):
    j+=1  
    good.append(good[j]*10+a)
    good.append(good[j]*10+b)
good.sort() 
good=[i for i in good if n*min(a,b)<=i<=n*max(a,b)]
ans=0 
MOD=10**9+7 
#print(good)
for x in range(0,n+1):
    if a*x+b*(n-x) in good:
        ans+=ncr(n,x,MOD)
        ans%=MOD 
print(ans)

# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
from typing import List
import functools
import operator as op

"""
created by shhuan at 2020/1/13 21:43

"""


MOD = 1000000007
MAXN = 10 ** 6 + 5
factorial = [0 for _ in range(MAXN)]
factorial[0] = 1
for i in range(1, MAXN):
    factorial[i] = factorial[i - 1] * i % MOD


def pow(a, b):
    if b == 0:
        return 1

    c = b // 2
    d = pow(a, c)
    if b % 2 == 0:
        return d * d % MOD
    return d * d * a % MOD


def inverse(k):
    return pow(k, MOD-2)


def ncr(n, k):
    k = min(k, n - k)
    return factorial[n] * inverse(factorial[k]) % MOD * inverse(factorial[n-k]) % MOD


def dlen(val):
    s = 0
    while val > 0:
        s += 1
        val //= 10

    return s


def gen(index, nbit, pre, a, b):
    if index >= nbit:
        return [pre]

    return gen(index + 1, nbit, pre * 10 + a, a, b) + gen(index + 1, nbit, pre * 10 + b, a, b)


def count(lo, hi, a, b, n, nnum):
    d = b - a
    ans = 0
    for v in gen(0, n, 0, a, b):
        if v < lo or v > hi:
            continue
        u = v - a * nnum
        if u % d == 0:
            y = u // d
            x = nnum - y
            # print(x, y, countab(lo, hi, a, b, x, y, n))
            # ans += countab(lo, hi, a, b, x, y, n)
            ans += ncr(nnum, x)
            # print(x, y, ncr(nnum, x))
            ans %= MOD
    return ans


def solve(N, A, B):
    lo, hi = N * A, N * B
    nl, nh = dlen(lo), dlen(hi)

    if nl == nh:
        return count(lo, hi, A, B, nl, N)
    else:
        return count(lo, 10 ** nl - 1, A, B, nl, N) + count(10 ** nl, hi, A, B, nh, N)


def test():
    N = 10 ** 6
    A = random.randint(1, 5)
    B = random.randint(1, 4) + A
    t0 = time.time()
    print(solve(N, A, B))
    print(time.time() - t0)

# print(solve(10**6, 2, 3))

A, B, N = map(int, input().split())
print(solve(N, A, B))

import math
from sys import stdin

#stdin=open('input.txt','r')
I=stdin.readline

mod=1000000007
fact = [1 for i in range(1000000+5)]
for i in range(2,len(fact)):
	fact[i]=fact[i-1]*i
	fact[i]%=mod

a,b,n=list(map(int,I().split()))
c1=chr(a+ord('0'))
c2=chr(b+ord('0'))
#byg=(math.factorial(1000000))
ans=0

for x in range(0,n+1):
	now=a*x+n*b-b*x
	flag=False
	for c in str(now):
		if(c!=c1 and c!=c2):
			flag=True
			break

	if(not flag):
		#print(x,now)
		now=fact[n]
		y=fact[x]
		z=fact[n-x]
		asd=pow(y*z,mod-2,mod)
		
		now*=asd
		now%=mod
		#now/=math.factorial(n-x)
		
		ans+=now
		ans%=mod

print(int(ans))



from math import factorial as fct 

MOD = 10**9 + 7
def c(n,k):
    return fct(n)//(fct(k)*fct(n-k))
 
def check(val,a,b):
    while val>0 :
        if val%10 == a or val%10 == b:
            val = val//10
        else:
            return False
    return True

a,b,n = list(map(int,input().split()))
f = [1]
for i in range(1, n + 1):
    f.append(f[-1] * i % MOD)
ans = 0

for i in range(n+1):
    if check(i*a + (n-i)*b,a,b):
        ans += pow(f[i]*f[n-i],MOD-2,MOD)
        ans %= MOD

print((ans*f[n])%MOD)


fact = [1]
mod = 10**9 + 7
def factorial(n):
    nonlocal  mod
    nonlocal  fact
    fact = [1]
    mod = 10**9 + 7
    for i in range(1,n+1):
        fact.append(fact[-1] * i)
        fact[-1] %= mod
def C(n,k):
    nonlocal mod
    return  (((fact[n]*pow(fact[k],mod-2,mod))%mod)*pow(fact[n-k],mod-2,mod))%mod
def good(x,a,b):
    while x > 0:
        if(x%10!=a and x%10!=b):
            return  False
        x//=10
    return  True
for _ in range(1):
    ans = 0
    a,b,n = map(int,input().split())
    factorial(n)
    for i in range(n+1):
        if(good(i*a+(n-i)*b,a,b)):
            ans += C(n,i)
            ans %= mod
    print(ans)

def R(): return list(map(int, input().split()))
def I(): return int(input())
def S(): return str(input())

def L(): return list(R())

from collections import Counter 

import math
import sys

from itertools import permutations


import bisect

mod=10**9+7

#print(bisect.bisect_right([1,2,3],2))
#print(bisect.bisect_left([1,2,3],2))

a,b,n=R()

fact=[1]*(n+1)

for i in range(1,n+1):
    fact[i]=fact[i-1]*i
    fact[i]%=mod

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def check(val,a,b):
    while val>0:
        if val%10!= a and val%10!=b:
            return False

        val//=10

    return True

ans=0
for i in range(n+1):
    if check(a*i+b*(n-i),a,b):
        ans+=fact[n]*modinv((fact[i]*fact[n-i])%mod,mod)
        ans%=mod


print(ans)


from bisect import bisect_left as bl, bisect_right as br, insort
import sys
import heapq
#from math import *
from collections import defaultdict as dd, deque
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
#def print(x): return sys.stdout.write(str(x)+'\n')
#sys.setrecursionlimit(100000)
mod=int(1e9+7)

def check(k):
    while k>0:
        x=k%10
        k//=10
        if x!=a and x!=b:
            return False
    return True

def fac(n):
    f=[0]*(n+1)
    f[0]=1
    for i in range(1,n+1):
        f[i]=(f[i-1]*i)%mod
    return f

a,b,n=mdata()
ans=0
f=fac(n)
for i in range(n+1):
    k=a*i+b*(n-i)
    if check(k):
        ans=(ans+int(pow(f[i]*f[n-i],mod-2,mod)))%mod
print((ans*f[n])%mod)


M=1000000007
import sys
def alele(): return list(map(int, sys.stdin.readline().strip().split()))
def ilele(): return map(int, sys.stdin.readline().strip().split())
def input(): return sys.stdin.readline().strip()
a,b,n=ilele();Ans=0
fact=[1]*(n+1)
for i in range(1,n+1):
	fact[i]=fact[i-1]*i%M;
for i in range(n+1):
    s=str(a*i+b*(n-i));Noa=0;Nob=0
    for j in s:
        if int(j)==a:Noa+=1
        elif int(j)==b:Nob+=1
    if Noa+Nob==len(s):Ans=(Ans+pow(fact[n-i]*fact[i],M-2,M))%M   
print((Ans*fact[n])%M)    

from math import factorial

MOD = 10**9+7
fact = {}

a, b, n = list(map(int, input().split()))
fact[0]=1
for i in range(1, n+1):
    fact[i] = fact[i-1]*i%MOD

ans = 0
for (i, j) in zip(list(range(n+1)), list(range(n, -1, -1))):
    if set(str(a*i + b*j)) <= {f'{a}', f'{b}'}:
        ans+=(fact[n]*pow(fact[n-i]*fact[i]%MOD, MOD-2, MOD) % MOD)
print(ans%MOD)


ans = 0
mod = 10**9+7
a, b, n = map(int, input().split())
s = set()
for x in range(2, 1 << 8):
    z = 0
    while x > 1:
        z = z * 10 + (a, b)[x & 1]
        x >>= 1
    s.add(z)
f = [1] * (n + 1)
for i in range(1, n + 1):
    f[i] = f[i - 1] * i % mod
for x in range(n + 1):
    if x * a + (n - x) * b in s:
        ans += pow(f[x] * f[n - x], mod - 2, mod)
        ans %= mod
print(ans * f[n] % mod)

import math
import time
from collections import defaultdict,deque,Counter
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
from queue import PriorityQueue 
import sys
MOD=int(1e9 +7)
def good(x):
    while(x>0):
        if(x%10!=a and x%10!=b):
            return False
        x=x//10
    return True
def ncr(n,r):
    return (fact[n]*pow(fact[i]*fact[n-i],MOD-2,MOD))%MOD
a,b,n=list(map(int,stdin.readline().split()))
fact=[1]*(n+2)
for i in range(1,n+1):
    fact[i]=fact[i-1]*i
    fact[i]%=MOD
ans=0
temp=b*n
for i in range(n+1):
    # print(i)
    if(good(temp)):
        ans+=ncr(n,i)
    temp+=a-b
print(ans%MOD)


ans = 0
mod = 1000000007
a, b, n = map(int, input().split())
s = set()
for x in range(2, 1 << 8):
    z = 0
    while x > 1:
        z = z * 10 + (a, b)[x & 1]
        x >>= 1
    s.add(z)
f = [1] * (n + 1)
for i in range(1, n + 1):
    f[i] = f[i - 1] * i % mod
for x in range(n + 1):
    if x * a + (n - x) * b in s:
        ans += pow(f[x] * f[n - x], mod - 2, mod)
        ans %= mod
print(ans * f[n] % mod)

N=10**6
mod=10**9+7
def checkgood(val, a, b):
    while(val):
        if(val%10 != a and val%10 !=b ):
            return False
        val//=10
    return(True)
def power(x, a):
    if(a==0):
        return(1)
    z=power(x, a//2)
    z = (z**2)%mod
    if(a%2):
        z=(z*x)%mod
    return(z)
fact=[1 for _ in range(N+1)]
for no in range(2, N+1):
    fact[no]=(fact[no-1]*no)%mod
[a, b, n]=list(map(int, input().split()))
count=0
for freq in range(n+1):
    val = freq*a+(n-freq)*b
    if(checkgood(val, a, b)):
        count+=(((fact[n]*power(fact[freq], mod-2))%mod)*power(fact[n-freq], mod-2))%mod
        count%=mod
print(count)