Из-за современной популярности глубокого обучения новые страны становятся похожими на нейросети. Это означает, что их строят глубоко с большим количеством уровней, на каждом уровне может находиться много городов. Так же у них есть ровно один вход и ровно один выход. Есть ровно L уровней, на каждом N городов. Давайте посмотрим на два соседних уровня L1 и L2. Каждый город из уровня L1 соединён с каждым городом из уровня L2 со стоимостью путешествия cij для 
, и для каждой пары соседних уровней эта стоимость одинакова (они просто копировали уровни, как всегда). Также стоимость проезда в каждый город L2 одинакова для всех городов из L1, то есть cij одинаково для 
и фиксированного j.
Доктор Ж. хочет ускорить его расчёты для этой страны и для этого он просит вас найти количество путей между точками входа и выхода, таких, что суммарная стоимость проезда будет делиться на заданное число M.
Выходные данные
Выведите одно число, число путей, которые может выбрать доктор Ж. так, чтобы полная стоимость проезда делилась бы на M, по модулю 109 + 7.
Примечание
Это страна с 3 уровнями, на каждом уровне по 2 города. Пути 
, и 
- единственные с полной стоимостью проезда, делящейся на 13. Обратите внимание, что все входящие в город рёбра имеют одинаковую стоимость и то, что они одинаковы для всех уровней.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3 13
4 6
2 1
3 4
|
2
|