2112. n+1=无见

据说,大荒原上那些铭碑下的遗迹,存留着大量和古代零迹人有关的信息。

pwp 跟着艾幻进入第零号遗迹探索,来到一扇大门前。门上只有一串不明的符文、一个拉杆和一段残断的通用语说明,似乎与如何开门有关。

那段说明中大致写道,类似的门后面还有很多,每扇门上都会有一串长度为 nn 的符文,这串符文中的每一个都可单独点亮或熄灭,只有每个符文都符合其该处于的状态(点亮或熄灭)时拉动机关,门才会开。

这串符文的亮暗应当服从以下规则:

  • 若约束 ai,j=0a_{i, j} = 0,在区间 [i,j][i, j] 中的符文应当同时被或不被点亮;
  • 若约束 ai,j=n+1a_{i, j} = n + 1,在区间 [i,j][i, j] 中应该同时存在被点亮和不被点亮的符文;
  • 若约束 ai,a_{i, }……

规则到这里就断了,约束 aa 倒是被完整保留下来。根据这些信息,pwp 希望知道至多需要尝试多少种情况才能将门打开——即使年代过于久远,已不知这些信息的真实性了。

输入

首先一行输入一个整数 n(2n3000)n (2 \le n \le 3000)

接下来有 nn 行,第 ii 行输入 ni+1n - i + 1 个整数,表示 ai,i,ai,i+1,,ai,n(0ai,jn+1)a_{i, i}, a_{i, i + 1}, \dots, a_{i, n}(0 \le a_{i, j} \le n + 1)

输出

输出一行一个整数,表示答案对 100000007100000007 取模的结果。

如果不存在能尝试的情况,输出 0 即可。

样例

标准输入 复制文本
3
0 3 4
1 2
0
标准输出 复制文本
6
标准输入 复制文本
3
0 0 4
0 3
2
标准输出 复制文本
2
标准输入 复制文本
3
2 0 4
4 0
0
标准输出 复制文本
0

来源

2024 软件学院 ACM 集训队筛选赛

登录以提交代码。
单点时限 2 秒
内存限制 512 MB
提交 6
通过 1