Cho dãy số \(a_{1}, a_{2}, \ldots, a_{n}\) và hai số \(k\) và \(s\). Bạn cần đếm số dãy số \(b_{1}, b_{2}, \ldots, b_{n}\) thoả mãn các điều kiện sau:

• \(b_{i} \in \{1, 2, \ldots, s\} \ \forall\ 1 \leq i \leq n\).
• Có chính xác \(k\) cặp chỉ số \((l, r)\) sao cho \(1 \leq l \leq r \leq n\) và dãy số \(a_{l}, a_{l + 1}, \ldots, a_{r − 1}, a_{r}\) có thứ tự từ điển nhỏ hơn dãy số \(b_{l}, b_{l + 1}, \ldots, b_{r − 1}, b_{r}\).

Do kết quả có thể rất lớn, bạn chỉ cần in ra phần dư của số dãy số thoả mãn khi chia cho \(20215201314\).

Nhắc lại, dãy số \(x_{1}, x_{2}, \ldots, x_{m}\) có thứ tự từ điển nhỏ hơn dãy số \(y_{1}, y_{2}, \ldots, y_{m}\) khi và chỉ khi tồn tại chỉ số \(\alpha\) sao cho:

• \(1 \leq \alpha \leq m, x_{\alpha} < y_{\alpha}\), và
• \(x_{\beta} = y_{\beta} \ \forall \ 1 \leq \beta \leq \alpha − 1\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, k\) và \(s\) \((1 \leq n \leq 2014, 0 \leq k \leq 9213, 1 \leq s \leq 902535)\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq s)\).

Output

• Gồm một số nguyên duy nhất là phần dư của số dãy số tìm được khi chia cho \(20215201314\).

Scoring

• Subtask \(1\) (\(10\) điểm): \(n \leq 8\) và \(s \leq 4\).
• Subtask \(2\) (\(10\) điểm): \(n \leq 12\).
• Subtask \(3\) (\(14\) điểm): \(n \leq 97\).
• Subtask \(4\) (\(12\) điểm): \(k = 0\).
• Subtask \(5\) (\(12\) điểm): \(k \leq 5 \times n\) và \(a_{1} = a_{2} = \ldots = a_{n} = 1\).
• Subtask \(6\) (\(12\) điểm): Không có ràng buộc gì thêm.

Example

4 6 3
2 3 2 1

7