şə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şrutda dəqiq şəhər var
Marşrutdakı bütün şəhərlər cüt-cüt müxtəlifdir
Marşrutun ümumi uzunluğu -ə bölünü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:
D_i + \ldots + D_{j - 1}, əgər i < j.
D_j + \ldots + D_{i - 1}, əgər j < i.
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.
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.
Marşrutların sayını 10^9+7 moduluna görə çıxarın.
Nümunə 1
Nümunə 2
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.