Emergency
Description
There is a square building consisting of $n \times n$ square rooms. Each room has four passages: to the north, to the south, to the east, and to the west. Some passages lead outside the building, while others connect pairs of adjacent rooms.
Your task is to draw an arrow in each room that will show which passage to follow in case of an emergency. Of course, the arrows must be drawn in such a way that, starting from any room and moving along the arrows, one can eventually exit the building.
You were confident that you knew the number of different ways to draw such arrows, but you have just discovered that some passages have been blocked. How many different ways are there to draw the arrows now?
The first line of input contains two integers $n$ and $k$ ($1 \le n \le 10$, $0 \le k \le 10$). The next $K$ lines describe the blocked passages. Each line contains four integers from $1$ to $n$, which are the coordinates of two adjacent rooms between which the passage is blocked. Each blocked passage is described only once.
Output a single integer: the number of different ways to draw the arrows modulo $10^9+7$.
Input
The first line of input contains two integers $n$ and $k$ ($1 \le n \le 10$, $0 \le k \le 10$). The next $K$ lines describe the blocked passages. Each line contains four integers from $1$ to $n$, which are the coordinates of two adjacent rooms between which the passage is blocked. Each blocked passage is described only once.
Output
Output a single integer: the number of different ways to draw the arrows modulo $10^9+7$.
2 0
2 4
1 1 1 2
1 1 2 1
2 2 1 2
2 2 2 1
192
16