Cerința

Se dă un vector cu n elemente care aparțin intervalului [1, p], iar modulul diferenței dintre oricare 2 valori consecutive este maxim k. Fane a șters câteva dintre numere, scriind in locul lor numărul 0. Aflați numărul de modalități de a completa numerele șterse de Fane, astfel încât vectorul să respecte cele 2 condiții.

Date de intrare

Programul citește de la tastatură numerele n, p, k, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul cerut modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ p ≤ 100
• 1 ≤ k ≤ 10

Exemplu:

Intrare

4 2 1
1 0 0 1

Ieșire

4

Explicație

Soluțiile sunt: {1, 1, 1, 1}, {1, 1, 2, 1}, {1, 2, 1, 1}, {1, 2, 2, 1}.