#1650. 幽冥公主

幽冥公主

Cannot parse: undefinedms error parsing time

题目描述

幽冥公主住在奥比斯山顶,她喜欢玩井字棋,但她觉得井字棋的状态量太少,不够纷杂,于是她想了一个新的游戏。

她告诉你一个 nn,表示棋盘大小为 nnnn 列,现在将棋盘进行黑白染色,有多少种方案使得棋盘不满足下列条件中的任何一条:

  1. 存在某行均为黑色;
  2. 存在某列均为黑色;
  3. 某对角线均为黑色。

由于这个题太难了,请输出 n=0n=0n=20n=20 时答案对 109+710^9 + 7 取模后的结果。

输入格式

没有输入。

输出格式

2121 行,第 ii 行表示 n=i1n=i-1 时的答案对 109+710^9 + 7 取模后的结果。

样例

样例输入


样例输出(仅显示前 55 行)

1
1
5
230
38154

数据范围与提示

程序总运行时间不应超过 11 小时(在学校的机子上,标程总运行时间为 15154040 秒,一种更简单的方法用时约 3030 分)。