Flowers and Chocolate

It's Piegirl's의 생일이 곧 다가오고, Pieguy는 그녀에게 꽃다발과 초콜릿 바구니를 사 주기로 했다.

꽃집에는 F가지 서로 다른 종류의 꽃이 있다. i-th번째 종류의 꽃은 항상 정확히 pi개의 꽃잎을 가진다. Pieguy는 정확히 N송이의 꽃으로 이루어진 꽃다발을 사기로 했다. 같은 종류의 꽃을 여러 번 살 수도 있다. 그런 다음 The N송이의 꽃을 꽃다발로 배열한다. 꽃다발 안에서 꽃의 위치는 중요하다. 꽃다발을 꽃 종류의 순서 있는 목록이라고 생각할 수 있다.

초콜릿 가게에서는 초콜릿을 상자에 담아 판매한다. B가지 서로 다른 종류의 상자가 있다. i-th번째 종류의 상자에는 초콜릿이 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로 나눈 나머지를 출력한다.

첫 번째 예제에서 꽃잎이 9개인 꽃다발을 만드는 방법은 1가지이고(3 + 3 + 3), 초콜릿이 9개인 바구니를 만드는 방법도 1가지이므로(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개 더 있다. 마지막으로 꽃잎이 15개인 꽃다발을 만드는 방법은 1가지이고(5 + 5 + 5), 초콜릿이 15개인 바구니를 만드는 방법도 1가지이므로(3 + 3 + 3 + 3 + 3), 조합이 1개 더 있다.

여러 꽃 종류의 꽃잎 수가 같을 수도 있다는 점에 유의한다. 그러한 종류들도 여전히 서로 다른 것으로 간주한다. 마찬가지로 서로 다른 종류의 상자에 같은 수의 초콜릿이 들어 있을 수도 있지만, 이들도 여전히 서로 다른 것으로 간주한다.