Cho ba số ~n~, ~m~, ~k~ và dãy ~b~ gồm ~n - m + 1~ phần tử, đếm số dãy ~a~ thỏa mãn:

• Dãy ~a~ gồm ~n~ phần tử;

• Mọi phần tử của dãy ~a~ đều có giá trị nằm trong khoảng từ ~1~ đến ~k~, hay ~1 \le a_i \le k~ với ~\forall\ 1 \le i \le n~;

• Nếu ~b_i \ne -1~ thì ~\displaystyle b_i = \max_{i \le j \le i + m - 1} a_j~ với ~\forall\ 1 \le i \le n - m + 1~.

Vì số lượng dãy ~a~ thỏa mãn có thể rất lớn, vì vậy chỉ cần đưa ra phần dư của kết quả trong phép chia cho ~1\ 000\ 000\ 007~.

Input

Vào từ file văn bản SEQUENCE.INP:

• Dòng đầu tiên chứa ba số nguyên dương ~n~, ~m~, ~k~ (~1 \le m \le n \le 100\ 000~, ~2 \le k \le 100\ 000~).

• Dòng thứ hai chứa ~n - m + 1~ số nguyên lần lượt là ~b_1, b_2, \dots, b_{n - m + 1}~ (~b_i = -1~ hoặc ~1 \le b_i \le k~).

Output

Ghi ra file văn bản SEQUENCE.OUT:

• Ghi ra trên một dòng duy nhất là phần dư của số dãy ~a~ thỏa mãn điều kiện đề bài trong phép chia cho ~1\ 000\ 000\ 007~.

Scoring

Sample Input 1

6 2 4
2 2 4 -1 1

Sample Output 1

5

Sample Input 2

6 3 2
-1 1 2 1

Sample Output 2

0

Notes

'Trong ví dụ đầu tiên, có ~5~ dãy ~a~ thỏa mãn đề bài:

• 1 2 1 4 1 1

• 1 2 2 4 1 1

• 2 1 2 4 1 1

• 2 2 1 4 1 1

• 2 2 2 4 1 1

Trong ví dụ thứ hai, không có dãy ~a~ nào thỏa mãn đề bài.