class construction():
    current = ""
    vals = []
    def constructInts(self,x:str,y:str,length:int):
        if len(self.current) == length:
            self.vals.append(self.current)
            self.current = self.current[0:-1]
            return
        for i in[x,y]:
            self.current += i
            self.constructInts(x,y,length)
        self.current = self.current[0:-1]
        return self.vals   
from typing import List
def barrels(d:List[int]):
    dict1 = {}
    new = construction()
    vals = new.constructInts(str(d[0]),str(d[1]),d[2])
    for i in vals:
        for k in i:
            if k not in dict1:
                dict1[k] = 1
            else:
                dict1[k] += 1
    return dict1[str(d[3])]% 1000000007
 

print(barrels([6,5,2,6]))
#new = construction()
#a = new.constructInts("5","6",3)