n міст розташовані на прямій в порядку 1,2,…,n, відстань між містами i та i+1 рівна Di для кожного i від 1 до n−1.
Вам потрібно порахувати кількість маршрутів, для яких виконуються наступні умови:
В маршруті рівно k міст
Всі міста в маршруті попарно різні
Сумарна довжина маршруту ділиться на m.
Сумарна довжина маршруту дорівнює сумі відстаней між містами, що йдуть в маршруті підряд. Відстань між містами i,j визначається за такою формулою:
Di+…+Dj−1, якщо i<j.
Dj+…+Di−1, якщо j<i.
Наприклад, якщо n=4 і D=[3,5,7], то довжина маршруту [3,1,4] дорівнює 8+15=23.
Виведіть кількість маршрутів за модулем 109+7.
У першому рядку містяться три цілі числа n,m,k(2≤n≤80,1≤m≤80,2≤k≤n) — кількість міст на прямій, число, на яке повинна ділитися сумарна довжина маршруту, і кількість міст в маршруті.
У наступному рядку містяться n−1 цілих чисел D1,D2,…,Dn−1 (1≤Di≤m) — відстані між сусідніми містами.
Виведіть кількість маршрутів за модулем 109+7.
В першому прикладі існує 4 такі маршрути:
2→3→4: довжина рівна 2+3=5.
4→3→2: довжина рівна 3+2=5.
1→3→2: довжина рівна (1+2)+2=5.
2→3→1: довжина рівна 2+(1+2)=5.