# Matrix Multiplication

Time Limit: 1000MS

Memory Limit: 131072K

## 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

## 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, ij), 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 1s in the 2006th power of the given matrix.

## Sample Input

3 4
1 2
2 1
0 1
0 2

## Sample Output

7

N/A