eolymp
Competitions

2021-2022 ICPC, SEERC, 1/8 Final

Шлях додому

$n$ міст розташовані на прямій в порядку $1, 2, \ldots, n$, відстань між містами $i$ та $i+1$ рівна $D_i$ для кожного $i$ від $1$ до $n-1$. Вам потрібно порахувати кількість маршрутів, для яких виконуються наступні умови: \begin{itemize} \item В маршруті рівно $k$ міст \item Всі міста в маршруті попарно різні \item Сумарна довжина маршруту ділиться на $m$. \end{itemize} Сумарна довжина маршруту дорівнює сумі відстаней між містами, що йдуть в маршруті підряд. Відстань між містами $i, j$ визначається за такою формулою: \begin{itemize} \item $D_i + \ldots + D_{j - 1}$, якщо $i < j$. \item $D_j + \ldots + D_{i - 1}$, якщо $j < i$. \end{itemize} Наприклад, якщо $n = 4$ і $D = [3, 5, 7]$, то довжина маршруту $[3, 1, 4]$ дорівнює $8 + 15 = 23$. Виведіть кількість маршрутів за модулем $10^9+7$. \InputFile У першому рядку містяться три цілі числа $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$) ~ --- відстані між сусідніми містами. \OutputFile Виведіть кількість маршрутів за модулем $10^9+7$. \Note В першому прикладі існує $4$ такі маршрути: \begin{itemize} \item $2 \to 3 \to 4:$ довжина рівна $2+3 = 5$. \item $4 \to 3 \to 2:$ довжина рівна $3+2 = 5$. \item $1 \to 3 \to 2:$ довжина рівна $(1+2)+2 = 5$. \item $2 \to 3 \to 1:$ довжина рівна $2+(1+2) = 5$. \end{itemize}
Time limit 8 seconds
Memory limit 256 MiB
Input example #1
4 5 3
1 2 3
Output example #1
4
Input example #2
15 17 6
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Output example #2
210690
Author Anton Trygub