/ 
Time Limit: 1 sec / Memory Limit: 256 MB
配点 : 200 点
問題文
N 行 N 列のタイルの各マスに、それぞれ 10^9 以下の正整数を 1 つずつ書いていきます。 ただし、全てのマスに正整数を書き終わった後に以下の条件を満たしている必要があります。
- どの縦、横、斜めに連続する 3 つのマスを選んでも、2 種類以上の正整数が含まれている。
あなたは、タイルに書く正整数の最大値 K をなるべく小さくしたいと考えています。 K の最小値を求めて下さい。また、K が最小値をとるような盤面の状態の個数を 10^9 + 7 で割った余りも求めて下さい。
制約
- N は整数である。
- 1 \leq N \leq 200
入力
入力は以下の形式で標準入力から与えられる。
N
出力
K の最小値と、K が最小値をとるような盤面の状態の個数を 10^9 + 7 で割った余りを空白区切りで 1 行に出力せよ。
入力例1
1
出力例1
1 1
連続する 3 マスがないので全て 1 で盤面を埋めることができ、盤面の状態は 1 通りである。
入力例2
2
出力例2
1 1
入力例3
4
出力例3
2 18
Score : 200 points
Problem Statement
You want to write a positive integer less than or equal to 10^9 in each cell of a tile with N rows and N columns. The tile must hold the following condition after you have written all positive integers.
- For any 3 consecutive cells that are aligned vertically, horizonally, or diagonally, the cells must contain at least 2 different positive integers.
You want to make the maximum integer K in the tile as small as possible. Find the minimum K and the number of the distinct states of tiles where K is the minimum value, modulo 10^9 + 7.
Constraints
- N is an integer.
- 1 \leq N \leq 200
Input
Input is given from Standard Input in the following format:
N
Output
Print the minimum K, and the number of the distinct states of tiles where K is the minimum value modulo 10^9 + 7, with a single space in between.
Sample Input 1
1
Sample Output 1
1 1
Since there are no 3 consecutive cells, you can fill every cell with 1 and the number of different states are 1.
Sample Input 2
2
Sample Output 2
1 1
Sample Input 3
4
Sample Output 3
2 18