Evə gedən yol#12852

Evə gedən yol

8 saniyə
256 meqabayt
Çox çətin

şəhər düz xətt üzərində 1, 2, \ldots, n ardıcıllığı ilə yerləşib və -dən n-1-ə qədər hər üçün və i+1 şəhərləri arasındakı məsafə D_i-yə bərabərdir.

Aşağıdakı şərtləri ödəyən marşrutların sayını hesablamaq lazımdır:

Marşrutun ümumi uzunluğu marşrutda ardıcıl gələn şəhərlər arasındakı məsafələrin cəminə bərabərdir. şəhərləri arasındakı məsafə aşağıdakı düsturla təyin olunur:

Məsələn, əgər n = 4 və D = [3, 5, 7] olarsa, [3, 1, 4] marşrutunun uzunluğu 8 + 15 = 23-ə bərabərdir.

Marşrutların sayını 10^9+7 moduluna görə çıxarın.

Giriş

Birinci sətirdə üç tam ədəd n, m, k (2 \le n \le 80, 1 \le m \le 80, 2 \le k \le n) — düz xətt üzərindəki şəhərlərin sayı, marşrutun ümumi uzunluğunun bölünməli olduğu ədəd və marşrutdakı şəhərlərin sayı verilir.

Növbəti sətirdə n - 1 tam ədəd D_1, D_2, \ldots, D_{n-1} (1 \le D_i \le m) — qonşu şəhərlər arasındakı məsafələr verilir.

Çıxış

Marşrutların sayını 10^9+7 moduluna görə çıxarın.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Qeyd

Birinci nümunədə belə marşrut var:

  • 2 \to 3 \to 4: uzunluq 2+3 = 5-ə bərabərdir.

  • 4 \to 3 \to 2: uzunluq 3+2 = 5-ə bərabərdir.

  • 1 \to 3 \to 2: uzunluq (1+2)+2 = 5-ə bərabərdir.

  • 2 \to 3 \to 1: uzunluq 2+(1+2) = 5-ə bərabərdir.