G. Цветы и шоколад
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скоро день рождения 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.

Примеры
Входные данные
2 3 3
3 5
10 3 7
Выходные данные
17
Входные данные
6 5 10
9 3 3 4 9 9
9 9 1 6 4
Выходные данные
31415926
Примечание

В первом примере есть 1 способ сделать букет с 9 лепестками (3 + 3 + 3), и 1 способ сделать корзинку с 9 кусочками шоколада (3 + 3 + 3), итого 1 комбинация. Есть 3 способа сделать букет с 13 лепестками (3 + 5 + 5, 5 + 3 + 5, 5 + 5 + 3), и 5 способов сделать корзинку с 13 кусочками шоколада (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 комбинацию.

Обратите внимание, что возможно существование нескольких типов цветов с одинаковым количеством лепестков. Такие типы все равно считаются различными. Аналогично, разные типы коробок тоже могут содержать равное число кусочков шоколада, но они считаются различными.