Шлях додому

$n$ міст розташовані на прямій в порядку $1,2,\dots ,n$, відстань між містами $i$ та $i+1$ рівна $D_i$ для кожного $i$ від $1$ до $n-1$.

Вам потрібно порахувати кількість маршрутів, для яких виконуються наступні умови:

• В маршруті рівно $k$ міст

• Всі міста в маршруті попарно різні

• Сумарна довжина маршруту ділиться на $m$.

Сумарна довжина маршруту дорівнює сумі відстаней між містами, що йдуть в маршруті підряд. Відстань між містами $i,j$ визначається за такою формулою:

• $D_i+\dots +D_{j-1}$, якщо $i<j$.

• $D_j+\dots +D_{i-1}$, якщо $j<i$.

Наприклад, якщо $n=4$ і $D=[3,5,7]$, то довжина маршруту $[3,1,4]$ дорівнює $8+15=23$.

Виведіть кількість маршрутів за модулем $10^9+7$.

Giriş verilənləri

У першому рядку містяться три цілі числа $n,m,k$($2\le n\le 80,1\le m\le 80,2\le k\le n$)  — кількість міст на прямій, число, на яке повинна ділитися сумарна довжина маршруту, і кількість міст в маршруті.

У наступному рядку містяться $n-1$ цілих чисел $D_1,D_2,\dots ,D_{n-1}$ ($1\le D_i\le m$)   — відстані між сусідніми містами.

Çıxış verilənləri

Виведіть кількість маршрутів за модулем $10^9+7$.

Nümunələr

Qeyd

В першому прикладі існує $4$ такі маршрути:

• $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$.