| Bubble Cup X - Finals [Online Mirror] |
|---|
| Закончено |
Из-за современной популярности глубокого обучения новые страны становятся похожими на нейросети. Это означает, что их строят глубоко с большим количеством уровней, на каждом уровне может находиться много городов. Так же у них есть ровно один вход и ровно один выход. Есть ровно 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. Обратите внимание, что все входящие в город рёбра имеют одинаковую стоимость и то, что они одинаковы для всех уровней.
