After experimenting with the Loop and Line models, you, the mayor of Grid Town, have come up with a more compact way to organize the town. Grid Town can be represented by a grid with $3$ rows and $M$ columns, labelled from $1$ to $3$ and $1$ to $M$ respectively. The square at row $i$ and column $j$ is denoted $(i,j)$.

For simplicity, Grid Town only has houses of two sizes, $1\times 1$ and $2\times 2$. You wish to cover the town with houses such that every square is occupied by a house. However, to achieve maximum strategic savings, you also require that the town is covered using the least number of houses possible.

To possibly reduce the number of houses needed, there are $K$ squares in the town where different houses may overlap (but are not required to). In other words, that square can be considered a part of multiple houses. No overlaps are allowed on the remainder of squares since residences of Grid Town dislike sharing.

As the mayor, you need to determine the minimum number of houses required to fill the town, and how many ways the town can be filled using this minimum number of houses.

Two arrangements of houses are considered different if there exists a square $(a,b)$ such that one of the following holds:

• One arrangement contains a house with its top left square at $(a,b)$ while the other arrangement does not.
• Both arrangements contain a house with its top left square at $(a,b)$ but the house dimensions are different.

Constraints

$2\le M\le {10}^9$

$0\le K\le min(2\times {10}^5,3\times M)$

$1\le a_i\le 3$

$1\le b_i\le M$

$(a_i,b_i)$ are pairwise-distinct.

Subtask 1 [5%]

$K=0$

Subtask 2 [10%]

$K=1$

Subtask 3 [20%]

$K=3\times M$

Subtask 4 [30%]

$M\le {10}^6$

Subtask 5 [35%]

No additional constraints.

Input Specification

The first line contains two integers $M$ and $K$.

The next $K$ lines each contain two integers $a_i$ and $b_i$, indicating that the square $(a_i,b_i)$ allows overlaps.

Output Specification

On the first line, output the minimum number of houses required to fill the town.

On the second line, output the number of ways of filling the town using the minimum number of houses. Since this number may be very large, please output it modulo ${10}^9+7$.

Sample Input 1

4 3
1 3
2 2
2 3

Sample Output 1

5
2

Explanation for Sample 1

The minimum number of houses required is $5$ and there are $2$ arrangements that use $5$ houses, which are shown below:

Sample Input 2

9 6
1 3
2 3
3 4
3 5
2 6
3 6

Sample Output 2

13
16

Sample Input 3

123 1
2 6

Sample Output 3

184
72793001