Eve giden yol#12852

Eve giden yol

8 saniye
256 megabayt
Çok zor

şehir bir doğru üzerinde 1, 2, \ldots, n sırasıyla yerleşmiştir ve 'den n-1'e kadar her için ile i+1 şehirleri arasındaki uzaklık D_i'ye eşittir.

Aşağıdaki koşulları sağlayan rotaların sayısını hesaplamanız gerekiyor:

Bir rotanın toplam uzunluğu, rotada ardışık gelen şehirler arasındaki uzaklıkların toplamına eşittir. şehirleri arasındaki uzaklık aşağıdaki formülle tanımlanır:

Örneğin, n = 4 ve D = [3, 5, 7] ise, [3, 1, 4] rotasının uzunluğu 8 + 15 = 23'e eşittir.

Rotaların sayısını 10^9+7 moduna göre yazdırın.

Giriş

İlk satırda üç tam sayı n, m, k (2 \le n \le 80, 1 \le m \le 80, 2 \le k \le n) — doğru üzerindeki şehirlerin sayısı, rotanın toplam uzunluğunun bölünmesi gereken sayı ve rotadaki şehirlerin sayısı verilir.

Sonraki satırda n - 1 tam sayı D_1, D_2, \ldots, D_{n-1} (1 \le D_i \le m) — komşu şehirler arasındaki uzaklıklar verilir.

Çıktı

Rotaların sayısını 10^9+7 moduna göre yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Not

Birinci örnekte bu tür rota vardır:

  • 2 \to 3 \to 4: uzunluk 2+3 = 5'e eşittir.

  • 4 \to 3 \to 2: uzunluk 3+2 = 5'e eşittir.

  • 1 \to 3 \to 2: uzunluk (1+2)+2 = 5'e eşittir.

  • 2 \to 3 \to 1: uzunluk 2+(1+2) = 5'e eşittir.