ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Open Ural FU Personal Contest 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. In Chinese Restaurant

Time limit: 1.0 second
Memory limit: 64 MB
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 ≤ mn). 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 ≤ kin; kii). 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

inputoutput
6 6
2
1
1
5
6
5
4
4 3
2
3
1
0
Problem Source: Open Ural FU Personal Contest 2013
To submit the solution for this problem go to the Problem set: 1962. In Chinese Restaurant