Description

Kobayashi went with the Galaxy Team players to a space contest. Influenced by the experience, he became more academic. After returning, he found the world had changed a lot. Biyomon underwent ultimate evolution and became Phoenixmon; Mr. Jin published a paper, was promoted to professor, and joined the Galaxy Team selection committee.

One day, Kobayashi chatted with Professor Jin. The professor recalled the years when he studied circuit theory. He was once very interested in a certain triangular wave and explored it. Kobayashi grew curious, so Professor Jin formalized the topic.

There is a continuous function $f(x)$ defined on $[0,N]$, where $N$ is an integer, satisfying $f(0)=f(N)=0$. All its extrema occur at integer points, and every local minimum of $f(x)$ is $0$. For any integer $I$ between $0$ and $N-1$, on $(I, I+1)$, $f(x)$ is a linear function with slope $1$ or $-1$.

What Mr. Jin studies is: if he knows the function values at $K$ integer points, then:

1. How many functions satisfy the conditions?
2. Among all functions that satisfy the conditions, what is the largest possible value of $\max f(x)$?

Kobayashi thought for a moment and came up with a good algorithm. What about you?

Input Format

The first line contains two integers $N, K$ separated by a space. The next $K$ lines each contain two integers, representing $x_i$ and $f(x_i)$.

Output Format

Output two integers in one line, corresponding to the answers to the two questions. Since the answer to the first question can be large, output it modulo $19940417$.

2 0

1 1

6 9
4 2
4 2
2 0
4 2
6 0
5 1
2 0
0 0
0 0

1 2

Hint

• For 10% of the testdata, $N \leq 10$.
• For 20% of the testdata, $N \leq 50$.
• For 30% of the testdata, $N \leq 100$, $K \leq 100$.
• For 50% of the testdata, $N \leq 10^3$, $K \leq 10^3$.
• For 70% of the testdata, $N \leq 10^5$.
• Additionally, for 10% of the testdata, $K=0$.
• For 100% of the testdata, $0 \leq N \leq 10^9$, $0 \leq K \leq 10^6$.

Translated by ChatGPT 5