```Description

Many studies have been done on developing efficient algorithms to calculate matrix multiplication.
But it remains as a hard topic today. In this problem you are to calculate the 2006th power of a
square Boolean matrix where addition and multiplication are defined as follows:

A B A + B
0 0   0
0 1   1
1 0   1
1 1   1

A B  AB
0 0   0
0 1   0
1 0   0
1 1   1

Truth Table of Multiplication

Let A be a square matrix. The zeroth power of A is the identity matrix.
The n-th (n > 0) power of A is the product of A and its (n ? 1)-th power.

Input

The input contains multiple test cases. Each test cases consists of some lines:

Line 1: Contains two integers K (K < 1000) and M (0 ¡Ü M ¡Ü 10K), indicating the dimension of
the matrix is K ¡Á K and K + M elements of the matrix are 1¡¯s.
Lines 2 ~ M + 1: Each contains two integers i and j (0 ¡Ü i, j < K, i ¡Ù j), indicating the
element in the (i + 1)-th row and (j + 1)-th column is 1.

All elements on the primary diagonal of the matrix are 1¡¯s.

Output

For each test case output one line containing the number of elements that are 1¡¯s in
the 2006th power of the given matrix.

Sample Input

3 4
1 2
2 1
0 1
0 2

Sample Output

7

Source

POJ Monthly--2006.07.30, Static

```