Anarchy Acres

Task

After spending a fortnight in Anarchy Acres you have come upon the problem of John's Porks.
Farmer John's farm has been in anarchy ever since he bought his $n$ naughty pigs. To bring back order, he has decided to turn exactly $k$ of them into officer pigs and hopes they will keep the rest in line. But not every choice of officers will lead to order on the farm.
We know the following:

• the pigs are all arranged in a line in a fixed order
• $o_i$ = the quantity of oats that pig number $i$ gets fed in a day
• in order to have a chance at order, the first and last pig must be turned into officers
• having order on the farm means all pigs are well-behaved

We also know that pigs are simple minded creatures, so they only notice the closest officer to their left and the closest to their right. And since pigs are so simple we can predict their behavior based on the following rules:

• an officer pig will always be well-behaved
• if a naughty pig gets strictly less oats than each of the two officers it sees, he will call this a systemic injustice and start a rebellion (will not be well-behaved)
• if a naughty pig gets strictly more oats than each of the two officers it sees, he will feel that he is above the law and start comitting crimes (will not be well-behaved)
• otherwise the naughty pig will be well-behaved

Help John by finding out how many ways of choosing $k$ officers will lead to order on his farm.

Two ways of choosing officers are considered different if there exists a pig chosen as officer in one but not in the other.

Input data

The first line of the input contains two positive integers $n$ ($1 \le n \le 2 \cdot 10^5$), representing the total number of pigs, and $k$ ($1 \le k \le 100$) representing the number of officer pigs.
The second line of the input contains $n$ integers $o_1$, $o_2$, $o_3$, ..., $o_n$ ($1 \le o_i \le 10^9$)

Output data

Let $M$ be the number of arrays $p_1$, $p_2$, $p_3$, ..., $p_k$ such that:

• $p_1$ = $1$
• $p_k$ = $n$
• $\min(o_{p_i}, o_{p_{i + 1}}) \le o_j \le \max(o_{p_i}, o_{p_{i + 1}})$, for all $i$ ($1 \le i \lt k$) and $j$ ($p_i \lt j \lt p_{i + 1}$)

Print the value of $M$ modulo $10^9 + 7$.

Example 1

stdin

10 7
3 15 3 19 3 3 8 20 7 2 

stdout

6

Explanation

There are $6$ ways to choose $7$ officers:

• $1$ $2$ $3$ $4$ $5$ $8$ $10$;
• $1$ $2$ $3$ $4$ $6$ $8$ $10$;
• $1$ $4$ $5$ $6$ $7$ $8$ $10$;
• $1$ $4$ $5$ $6$ $8$ $9$ $10$;
• $1$ $4$ $5$ $7$ $8$ $9$ $10$;
• $1$ $4$ $6$ $7$ $8$ $9$ $10$.

Example 2

stdin

14 8
14 7 13 13 11 12 2 10 11 9 4 7 3 11 

stdout

8

Explanation

There are $8$ ways to choose $8$ officers:

• $1$ $2$ $3$ $4$ $5$ $6$ $7$ $14$;
• $1$ $2$ $3$ $4$ $7$ $9$ $13$ $14$;
• $1$ $2$ $3$ $7$ $8$ $9$ $13$ $14$;
• $1$ $2$ $3$ $7$ $9$ $10$ $13$ $14$;
• $1$ $2$ $4$ $7$ $8$ $9$ $13$ $14$;
• $1$ $2$ $4$ $7$ $9$ $10$ $13$ $14$;
• $1$ $7$ $8$ $9$ $11$ $12$ $13$ $14$;
• $1$ $7$ $9$ $10$ $11$ $12$ $13$ $14$.

Example 3

stdin

15 8
5 19 8 7 7 19 19 15 10 11 9 10 9 10 2 

stdout

66