## 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 Truth Table of Addition 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