When Vova arrived in Guangzhou, his Chinese friends immediately invited him to
a restaurant. Overall n people came to the restaurant, including Vova.
The waiter offered to seat the whole company at a traditional large round
table with a rotating dish plate in the center.
As Vova was a guest, he got the honorable place by the door. Then m
people in the company stated that they wanted to sit near a certain
person. Your task is to determine the number of available arrangements to
seat Vova's friends at the table.
Input
The first line contains integers n and m (2 ≤ n ≤ 100;
0 ≤ m ≤ n). The next m lines contain integers k1,
…, km, where ki is the number of the person who the person
number i wants to sit with (1 ≤ ki ≤ n; ki ≠ i). Being an
honorable guest, Vova got number 1. His friends are numbered with
integers from 2 to n.
Output
Print the number of available arrangements to seat Vova's friends modulo 109 + 7.
Samples
input | output |
---|
6 6
2
1
1
5
6
5
| 4
|
4 3
2
3
1
| 0
|
Problem Source: Open Ural FU Personal Contest 2013