Zero Sequence
Limits: 2 sec., 256 MiB
You have a sequence of \(N\) zeros. You have to replace \(K\) of them with positive integers \(A_1, A_2, ..., A_K\) in such way that each positive integer \(C\) is surrounded by at least \(C\) consecutive zeroes from the left and with at least \(C\) consecutive zeros from the right. These zeros have to appear just before and just after the number \(C\) itself: \(..., 0, 0, ..., 0, C, 0, 0, ..., 0, ...\).
You have to find the number of distinct sequences you can get by replacing exactly \(K\) zeros and print it modulo 1234567891.
Input
The first line contains two integers \(N\) and \(K\) separated by a single space. The following line contains \(N\) integers \(A_1, A_2, ..., A_K\) separated by single spaces.
Output
The number of sequences modulo 1234567891.
Constraints
\(1 \le N \le 1000\),
\(1 \le K \le 100\),
\(1 \le A_j \le 100\).
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 10 3 1 2 1 | 12 |
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|