ş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:
Rota tam olarak şehir içerir
Rotadaki tüm şehirler ikişerli olarak farklıdır
Rotanın toplam uzunluğu 'ye bölünür.
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:
D_i + \ldots + D_{j - 1}, eğer i < j ise.
D_j + \ldots + D_{i - 1}, eğer j < i ise.
Ö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.
İ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.
Rotaların sayısını 10^9+7 moduna göre yazdırın.
Örnek 1
Örnek 2
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.