马上就要到 Piegirl 的生日了,Pieguy 决定给她买一束鲜花和一篮巧克力。
花店有F种不同类型的鲜花可供选择。第 i 种花的花瓣总是恰好为 pi 。 Pieguy 决定购买一束恰好由 N 朵花组成的花束。他可能会多次购买同一种花。然后将N朵花排列成花束。鲜花在花束中的位置很重要。您可以将花束视为花卉类型的有序列表。
巧克力店出售盒装巧克力。有 B 种不同类型的盒子可供选择。第 i 类盒子包含 ci 块巧克力。 Pieguy可以购买任意数量的盒子,并且可以多次购买相同类型的盒子。然后他会将这些盒子放入篮子中。盒子在篮子内的位置很重要。您可以将篮子视为盒子类型的有序列表。
Pieguy 知道 Piegirl 喜欢在吃每块巧克力之前先从花上摘下一片花瓣。他想确保她在摘下最后一朵花的最后一片花瓣后,吃掉最后一个盒子里的最后一块巧克力。也就是说,花束中所有花朵上的花瓣总数应等于篮子中所有盒子中巧克力的总数。
Pieguy 可以购买多少种不同的花束+篮子组合?答案可能非常大,因此请以 1000000007 = 109 + 7 为模进行计算。
输入
输入的第一行将分别包含整数 F、B 和 N(1 ≤ F ≤ 10、1 ≤ B ≤ 100、1 ≤ N ≤ 1018)、鲜花类型数量、盒子类型数量以及花束中必须放入的鲜花数量。
输入的第二行将包含 F 个整数 p1, p2, ..., pF (1 ≤ pi ≤ 109),即每种花类型的花瓣数量。
输入的第三行将包含 B 个整数 c1, c2, ..., cB (1 ≤ ci ≤ 250),即每种盒子类型中巧克力的数量。
输出
打印 Pieguy 可以购买的花束+篮子组合的数量,模 1000000007 = 109 + 7。
示例
输入 #1
2 3 3 3 5 10 3 7
输出 #1
17
输入 #2
6 5 10 9 3 3 4 9 9 9 9 1 6 4
输出 #2
31415926
注意
在第一个示例中,有 1 种方法制作 9 片花瓣 (3 + 3 + 3) 的花束,有 1 种方法制作 9 块巧克力 (3 + 3 + 3) 的篮子,有 1 种可能的组合。制作 13 片花瓣的花束有 3 种方法(3 + 5 + 5、5 + 3 + 5、5 + 5 + 3),制作 13 块巧克力的篮子有 5 种方法(3 + 10、10 + 3、3 + 3 + 7、3 + 7 + 3、7 + 3 + 3),还有 15 种组合。最后,有 1 种方法制作 15 片花瓣 (5 + 5 + 5) 的花束,还有 1 种方法制作 15 块巧克力的篮子 (3 + 3 + 3 + 3 + 3),还有 1 种组合。
请注意,多种类型的花可能具有相同数量的花瓣。这些类型仍然被认为是不同的。同样,不同类型的盒子可能包含相同数量的巧克力,但仍然被认为是不同的。