硬币凑数

#encoding:utf-8
_author_ = "Wang Wenchao"
'''
现在有n1 +n2种面值的硬币，其中前n1中为普通币，
可以取任意枚，后n2种为纪念币，每种最多只能取一枚，
每种硬币有一个面值，问能有多少种方法拼出m的面值。
输入第一行为n1，n2，m
第二行和第三行分别为普通币和纪念币的面值
'''
line=raw_input()
line=line.split(' ')
n1,n2,m=int(line[0]),int(line[1]),int(line[2])
a=raw_input()
a=[int(k) for k in a.split(' ')]
#print a
b=raw_input()
b=[int(k) for k in b.split(' ')]
#print b
res=[0]*(m+1)
for ra in a:
    for i in range(1,m+1):
        if i%ra==0:
            res[i]+=1
        elif res[i]>0:
            if i+ra<=m:
                res[i+ra]+=res[i]
                res[i+ra]%=1000000007
        else:
            pass
    #print res
for rb in b:
    temp=[f for f in res]
    for i in range(1,m+1):
        if res[i]>0:
            if i+rb<=m:
                res[i+rb]+=temp[i]
                res[i + rb] %= 1000000007
        res[i]+=1
#print res
print res[m]