Problem Description

Xiao Lin accompanied the Galaxy Team players to a cosmic competition, where he was influenced by the academic atmosphere. Upon returning, he found the world had drastically changed. Biyomon had evolved into Phoenixmon; Mr. Jin, having published a paper, had become a professor and a member of the Galaxy Team selection committee.

One day, Xiao Lin chatted with Professor Jin. The professor reminisced about the past and the circuit principles he had studied. He was particularly interested in a triangular wave and had conducted some research. Xiao Lin was curious, so Professor Jin formalized the problem 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 are at integer points, and all its local minima 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 \((I, I+1)\).

Professor Jin's research question is: if he knows the function values at \( K \) integer points, then:

1. How many functions satisfy these conditions?
2. Among the functions that satisfy the conditions, what is the maximum possible value of \( f(x) \)?

Xiao Lin thought for a moment and came up with a good algorithm. How about you, who have been trained for many years?

Input Format

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

Output Format

One line with two integers, corresponding to the answers to the two questions. Considering the first answer may be very large, output it modulo \( 19940417 \).

Sample Input and Output

Sample Input #1

2 0

Sample Output #1

1 1

Sample Input #2

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

Sample Output #2

1 2

Notes

• For \( 10\% \) of the data, \( N \leq 10 \).
• For \( 20\% \) of the data, \( N \leq 50 \).
• For \( 30\% \) of the data, \( N \leq 100 \), \( K \leq 100 \).
• For \( 50\% \) of the data, \( N \leq 10^3 \), \( K \leq 10^3 \).
• For \( 70\% \) of the data, \( N \leq 10^5 \).
• Additionally, \( 10\% \) of the data has \( K = 0 \).
• For \( 100\% \) of the data, \( 0 \leq N \leq 10^9 \), \( 0 \leq K \leq 10^6 \).

见题面 Input 部分

见题面 Output 部分