Problem Description

We will write a positive integer less than or equal to $10^9$ on each square of an $N \times N$ grid. However, after writing all the integers, the following condition must be satisfied:

• For any three consecutive squares in a row, column, or diagonal, they must contain at least two different positive integers.

You want to minimize the maximum value $K$ of the integers written on the tiles. Find the minimum value of $K$ and also find the number of states of the board that achieve this minimum value, modulo $10^9 + 7$.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the minimum value of $K$ and the number of states of the board that achieve this minimum value, modulo $10^9 + 7$, separated by a space in one line.

Sample Input and Output

Sample Input #1

1

Sample Output #1

1 1

Sample Input #2

2

Sample Output #2

1 1

Sample Input #3

4

Sample Output #3

2 18

Notes/Hints

Constraints

• $ N $ is an integer.
• $1 \leq N \leq 200$

Sample Explanation 1

Since there are no three consecutive squares, the board can be filled with all $1$s, and there is only $1$ state of the board.

见题面 Input 部分

见题面 Output 部分