Complex ascents

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Today Zenyk and Marichka conquered \(n\) peaks in the Carpathians. Zenyk has an old mountain guidebook where the difficulty of the ascent for each peak is denoted by a positive integer not exceeding \(k\). Note that different peaks can have the same difficulty.

At each peak during a rest, our heroes counted the number of peaks they had visited before this one with a difficulty no greater than the one where they currently are. Then Zenyk wrote this number in his notebook.

In the evening, comfortably settled in their tent, Marichka is boasting to her friends about her mountain adventures in a live broadcast. She talks about how interesting and at the same time difficult it was to overcome the Carpathian routes. To prove her words, Marichka demonstrates the entries in Zenyk’s notebook, and her friends try to figure out how difficult the ascents were. However, reconstructing the sequence of ascent difficulties based on Zenyk’s notes is not so simple. Moreover, there can be several such sequences, or none at all if Zenyk made a mistake. Help Marichka find the number of such sequences that correspond to the recorded information.

Input

The first line contains two integers \(n\) and \(k\) separated by a space. The second line gives \(n\) integers separated by spaces \(c_1, \ldots, c_n\) — the entries in Zenyk’s notebook.

Output

The number of different sequences that correspond to Zenyk’s notes, modulo \(10^9+7\).

Constraints

\(1 \le n, k \le 10^5\),

\(0 \le c_i < n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 0 1 2 1	5

Notes

For example, the following ascent difficulty sequences correspond to Zenyk’s notes:

• 1 2 2 1

• 1 2 3 1

• 1 3 3 1

• 1 3 3 2

• 2 3 3 2