AT_kupc2017_d.Sanmoku

在一个 $N$ 行 $N$ 列的方格中，每个格子里都要写上一个不超过 $10^9$ 的正整数。填写完所有格子后，需要满足以下条件：

• 对于任意连续的 $3$ 个格子（无论是横向、纵向还是斜向），其中必须包含至少 $2$ 种不同的正整数。

你希望填写的最大正整数 $K$ 尽可能小。请你求出 $K$ 的最小值，以及当 $K$ 取最小值时可能的棋盘状态数对 $10^9+7$ 取余的结果。

输入从标准输入读入，格式如下：

$N$

请输出 $K$ 的最小值和对应的棋盘状态数对 $10^9+7$ 取余的结果，使用一个空格隔开，输出在一行中。

限制

• $N$ 是整数。
• $1 \leq N \leq 200$

样例解释 1

因为不存在连续的 $3$ 个格子，所以所有格子都可以填写 $1$，棋盘状态只有 $1$ 种。

由 ChatGPT 5 翻译