Problems
Шлях додому
Шлях додому
$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}
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