Triangular Wave Functions

A continuous function f(x) is defined on the interval \([0, N]\), where \(N\) is an integer. The function satisfies \(f(0)=f(N)=0\), and all its extreme points occur only at integer coordinates. Moreover, every local minimum of f(x) is exactly 0. For any integer \(I\) with \(0 \le I \le N-1\), the restriction of f(x) on the open interval \((I, I+1)\) is a linear function with slope either \(+1\) or \(-1\>.

Professor Jin, recalling his studies on circuits and a peculiar triangular wave, considers the following problem. You are given the values of f(x) at exactly \(K\) distinct integer points. (Note that the endpoints \(f(0)=0\) and \(f(N)=0\) are always fixed even if not given explicitly.)

Your task is to determine:

1. The number of functions satisfying the above conditions and matching the given \(K\) fixed values. Since the answer can be very large, output it modulo \(10^9+7\).
2. Among all such functions, what is the maximum possible value of f(x) (i.e. the highest peak the function can reach)?

Notes:

• The function f(x) is piecewise linear. Its graph is completely determined by its values at integer points. For any interval between two consecutive fixed integers \(x_1\) and \(x_2\) with values \(f(x_1)=a\) and \(f(x_2)=b\), the function consists of \(L=x_2-x_1\) line segments, each with slope either \(+1\) or \(-1\). In any such segment, if you choose the pattern of slopes to maximize the peak, the highest value attained is \(\frac{L + a + b}{2}\) (this value is always an integer when a valid function exists).
• In addition to the usual non‐negativity constraint \(f(x)\ge 0\) (so that the only minima can be 0), there is an extra restriction: if an interior integer point is not 0 then it cannot be a local minimum. In other words, if for some integer \(i\) with \(0 < i 0\), then it cannot happen that \(f(i-1)=f(i)+1\) and \(f(i+1)=f(i)+1\) simultaneously.

You are to use the given fixed values to split the interval \([0, N]\) into segments. For each segment, count the number of valid ways to assign values (using dynamic programming, for example) that satisfy the slope conditions and the restrictions described above. The final answer is the product (modulo \(10^9+7\)) over all segments. Also, by choosing the slopes appropriately you can maximize the peak in each segment to obtain the overall maximum value of f(x).

inputFormat

The first line contains two integers \(N\) and \(K\) (with \(N \ge 1\) and \(K \ge 0\)).

The following \(K\) lines each contain two integers \(P\) and \(V\) indicating that at the integer point \(x=P\), \(f(P)=V\). It is guaranteed that \(0 \le P \le N\). Note that the endpoints \(f(0)=0\) and \(f(N)=0\) are fixed by the problem conditions even if not provided in the input.

outputFormat

Output two space‐separated integers on one line:

1. The number of functions satisfying the conditions (modulo \(10^9+7\)).
2. The maximum possible value of f(x) among all such functions.

sample

2 0

1 1