In the country of Spadana, people are very interested in Sufism and Sufis. For this reason, every year on one day, especially the Sufis perform a show to guide everyone.
in this country
n
n Sufis live with numbers
1
1 to
n
n are specified. Every Sufi has a meaning and the meaning of a Sufi
i
i Um, Sufi
i
-
1
i−1 is om and the Sufi meaning is no
1
1 is also God.
this
n
n Sufis perform the show in one line. this line
n
+
1
It has n+1 places with numbers
0
0 to
n
n are numbered from left to right. At first, the Sufis in the positions
1
,
2
,
.
.
.
,
n
1,2,...,n are located so that no two Sufis are in the same position. In this symbolic representation, God is always at the zero position of the line.
This show is done in such a way that the gun is fired twice in each stage.

With the first shot of the gun, each Sufi looks at his target and remembers his position, then if his target's position was to his left, he decides to move one unit to the left, if his target's position is the same as his own, he decides not to move and If he meant his right, he decides to go one unit to the right.

With the second shot of the gun, each Sufi performs the movement he intended in the previous step. (may remain in place)

The show ends when all the Sufis are at zero and reach their true purpose. Please note that during these steps, more than one Sufi may be placed in the same position.
For example, suppose the initial position of the Sufis is as follows, the steps will be like this. (We have shown God with the number zero)

<

0

∣

3

∣

1

∣

2

>

→

<

0

∣

1

∣

2
,
3

∣

>

→

<

0
,
1

∣

2

∣

3

∣

>

→

<

0
,
1
,
2

∣

3

∣

∣

>

→

<

0
,
1
,
2
,
3

∣

∣

∣

>
< 0 ∣ 3 ∣ 1 ∣ 2 > → < 0 ∣ 1 ∣ 2,3 ∣ > → < 0,1 ∣ 2 ∣ 3 ∣ > → < 0,1,2 ∣ 3 ∣ ∣ > → < 0,1,2 ,3 ∣ ∣ ∣ >

In the above example, the positions with
∣
∣ have been separated and each Sufi has found out which position he is in.

The beauty of a show in the eyes of people is the number of stages. For example, the beauty of the show above,
4
is 4. Now, on the eve of the performance, the position of a number of Sufis has been determined, but the rest of the Sufis have not yet determined their initial position. Suppose the number of Sufis whose initial position is not known
k
be k Write a program that calculates the sum of the beauty of all possible representations, i.e. the sum of the beauty of the representations for all the states in which the Sufis whose initial position is unknown can be placed in the empty positions. (
k
!
k! possible state) since this number may be large, its remainder in the measure
1
0
9
+
7
10
9
 Find +7.

input
The first line of input contains two numbers
n
,
k
n, k that
n
n number of Sufis and
k
k specifies the number of Sufis whose starting position is unknown.
In the second line
n
n number
a
1
,
a
2
,
.
.
.
,
a
n
a
1
​
 , a
2
​
 ,...,a
n
​
 It comes that
a
i
a
i
​
 The Sufi number is in the position
i
i is located
If
a
i
=
-
1
a
i
​
 =−1 means that this place has not been determined which Sufi place it is.

for every
i
i and
J
j distinct that
a
i
,
a
J
≠
-
1
a
i
​
 , a
J
​


=−1 we know
a
i
≠
a
J
a
i
​


=a
J
​

number
i
The i's that
a
i
=
-
1
a
i
​
 =−1 is equal to
k
k is
1
≤
n
≤
1
0
5
1≤n≤10
5

0
≤
k
≤
m
i
n
(
n
,
100
)
0≤k≤min(n,100)
a
i
=
-
1
a
i
​
 =−1 or
1
≤
a
i
≤
n
1≤a
i
​
 ≤n
output
In the only output line, print the answer to the problem.

Sub-problems
Constraints score subproblem
1 8
n
≤
1000
n≤1000,
k
=
0
k=0
2 31
k
=
0
k=0
3 23
k
=
n
k=n
4 38 without additional restrictions
Example
Sample entry 1
3 0
3 1 2
Plain text
Sample output 1
4
Plain text
Sample input 2
3 2
3-1-1
Plain text
Sample output 2
9 c++