Шлях додому#10768
міст розташовані на прямій в порядку 1, 2, \ldots, n, відстань між містами та i+1 рівна D_i для кожного від до n-1.
Вам потрібно порахувати кількість маршрутів, для яких виконуються наступні умови:
В маршруті рівно міст
Всі міста в маршруті попарно різні
Сумарна довжина маршруту ділиться на .
Сумарна довжина маршруту дорівнює сумі відстаней між містами, що йдуть в маршруті підряд. Відстань між містами визначається за такою формулою:
D_i + \ldots + D_{j - 1}, якщо i < j.
D_j + \ldots + D_{i - 1}, якщо j < i.
Наприклад, якщо n = 4 і D = [3, 5, 7], то довжина маршруту [3, 1, 4] дорівнює 8 + 15 = 23.
Виведіть кількість маршрутів за модулем 10^9+7.
У першому рядку містяться три цілі числа n, m, k (2 \le n \le 80, 1 \le m \le 80, 2 \le k \le n) — кількість міст на прямій, число, на яке повинна ділитися сумарна довжина маршруту, і кількість міст в маршруті.
У наступному рядку містяться n - 1 цілих чисел D_1, D_2, \ldots, D_{n-1} (1 \le D_i \le m) — відстані між сусідніми містами.
Виведіть кількість маршрутів за модулем 10^9+7.
Приклад 1
Приклад 2
В першому прикладі існує такі маршрути:
2 \to 3 \to 4: довжина рівна 2+3 = 5.
4 \to 3 \to 2: довжина рівна 3+2 = 5.
1 \to 3 \to 2: довжина рівна (1+2)+2 = 5.
2 \to 3 \to 1: довжина рівна 2+(1+2) = 5.