B. Страны - нейросети
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Из-за современной популярности глубокого обучения новые страны становятся похожими на нейросети. Это означает, что их строят глубоко с большим количеством уровней, на каждом уровне может находиться много городов. Так же у них есть ровно один вход и ровно один выход. Есть ровно L уровней, на каждом N городов. Давайте посмотрим на два соседних уровня L1 и L2. Каждый город из уровня L1 соединён с каждым городом из уровня L2 со стоимостью путешествия cij для , и для каждой пары соседних уровней эта стоимость одинакова (они просто копировали уровни, как всегда). Также стоимость проезда в каждый город L2 одинакова для всех городов из L1, то есть cij одинаково для и фиксированного j.

Доктор Ж. хочет ускорить его расчёты для этой страны и для этого он просит вас найти количество путей между точками входа и выхода, таких, что суммарная стоимость проезда будет делиться на заданное число M.

Входные данные

Первая строка ввода содержит N (1 ≤ N ≤ 106) –– число стран в слое, L (2 ≤ L ≤ 105) – число уровней, и M (2 ≤ M ≤ 100).

Вторая, третья и четвёртые строки содержат N целых чисел, 0 ≤ cost ≤ M обозначающих цену проезда от точки входа до первого уровня, цены проезда между соседними уровнями, как описано выше, и цены проезда от последнего уровня до точки выхода.

Выходные данные

Выведите одно число, число путей, которые может выбрать доктор Ж. так, чтобы полная стоимость проезда делилась бы на M, по модулю 109 + 7.

Пример
Входные данные
2 3 13
4 6
2 1
3 4
Выходные данные
2
Примечание

Это страна с 3 уровнями, на каждом уровне по 2 города. Пути , и - единственные с полной стоимостью проезда, делящейся на 13. Обратите внимание, что все входящие в город рёбра имеют одинаковую стоимость и то, что они одинаковы для всех уровней.