Xiao Lin went on a space competition with the Galaxy Team and became quite academic after being influenced by the environment. Upon returning, he found that the world had changed significantly. Biyomon had digivolved into Hououmon; Mr. Jin had become a professor overnight after publishing a paper and had also become a member of the Galaxy Team selection committee.

One day, Xiao Lin was chatting with Professor Jin. The professor recalled the past, specifically the circuit theory he had studied in those years. He had once been very interested in a type of triangular wave and had conducted some research on it. Xiao Lin was curious, so Professor Jin formalized the topic for him.

Consider a continuous function $f(x)$ defined on $[0, N]$, where $N$ is an integer, satisfying $f(0)=f(N)=0$. All its extreme points occur at integer coordinates, and all local minima of $f(x)$ are $0$. For any integer $I$ between $0$ and $N-1$, $f(x)$ is a linear function with a slope of $1$ or $-1$ on the interval $(I, I+1)$.

Professor Jin is researching the following: if he knows the function values at $K$ integer points, then: (1) How many such functions satisfy the conditions? (2) Among the functions that satisfy the conditions, what is the maximum possible value of $\max f(x)$?

Xiao Lin thought for a moment and came up with a great algorithm. What about you, after years of training?

Input

The first line contains two space-separated integers $N$ and $K$. The next $K$ lines each contain two integers, representing $x[i]$ and $f(x[i])$.

Output

A single line containing two integers, corresponding to the answers to the two questions, respectively. Since the answer to the first question may be very large, you only need to output it modulo $19940417$.

Examples

Input 1

2 0

Output 1

1 1

Constraints

• For $10\%$ of the data, $N \le 10$.
• For $20\%$ of the data, $N \le 50$.
• For $30\%$ of the data, $N \le 100, K \le 100$.
• For $50\%$ of the data, $N \le 1000, K \le 1000$.
• For $70\%$ of the data, $N \le 100000$.
• Additionally, for $10\%$ of the data, $K=0$.
• For $100\%$ of the data, $0 \le N \le 1000000000, 0 \le K \le 1000000$.