Gats and the Rising Rooftops

Time limit: 2000 msMemory limit: 256 MB

Gats is exploring a rectangular grid of rooftops with $R$ rows and $C$ columns. Rooftop $(i,j)$ has height $H_{i,j}$ . He starts at rooftop $(1,1)$ and wants to reach rooftop $(R,C)$ .

From rooftop $(i,j)$ , Gats may jump either rightward or downward. He always lands on the first rooftop in the chosen direction that is strictly higher than his current rooftop:

For a rightward jump, if there is at least one column $k$ satisfying $j < k \le C$ and $H_{i,k} > H_{i,j}$ , he lands at for the smallest such .

If no strictly higher rooftop exists in the chosen direction, that jump is unavailable. Gats cannot jump leftward or upward.

A route is the sequence of rooftops on which Gats lands, including the starting and destination rooftops. Two routes are distinct if their sequences differ.

Determine the minimum number of jumps needed to reach $(R,C)$ and the number of distinct routes that use exactly that minimum number of jumps. If $(1,1) = (R,C)$ , the minimum is $0$ jumps and there is exactly route.

Input

The first line contains two integers $R$ and $C$ ( $1 \le R, C \le 2000$ , $R \times C \le 10^6$ ), the number of rows and columns in the grid.

Output

Print two integers $J$ and $W$ separated by a space.

If Gats can reach $(R,C)$ , then $J$ is the minimum number of jumps required and $W$ is the number of distinct routes using exactly jumps, taken modulo .

Samples

Sample 1

Input

Output

4 6

Gats needs at least $4$ jumps. There are $6$ distinct routes that use exactly $4$ jumps.

Sample 2

Input

Output

3 1

The destination can be reached in $3$ jumps, and exactly one route uses that many jumps.

Sample 3

Input

2 2
4 3
2 1

Output

-1 0

Every rooftop to the right or below the starting rooftop is lower, so Gats cannot make a first jump.

Gats and the Rising Rooftops

Input

Output

Samples

Sample 1

Sample 2

Sample 3

Submit

Submissions