渝
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}⭐我喜欢海棠花不眠
\hspace{15pt}可惜一切都来不及了...
\hspace{15pt}Bingbong 拿到一个由数字 0 和 1 组成的三角形，一共有 n 行，第 i 行有 i 个数字。我们使用 (i,j) 表示从上往下数第 i 行和从左往右数第 j 列的位置，使用 a_{i,j} 代表这个单元格中的数字。
\hspace{15pt}Bingbong 初始时位于 (1,1)，她每次移动会选择移动到 (i+1,j) 或者 (i+1,j+1)，每到一个位置会得到该位置的元素值，记作 b_i。
\hspace{15pt}最终移动到第 n 行时，共得到了 n 个元素，通过拼接后，我们记作 b_{1}b_{2}b_{3}\cdots b_{n}，即字符串 b。
\hspace{15pt}现在请你求出到达第 n 行后，有多少条路径满足字符串 b 是一个回文串。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。

\hspace{15pt}一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1\leqq n\leqq 500\right)，表示行数。 
\hspace{15pt}此后 n 行，第 i 行输入 i 个整数 a_{i,1}, a_{i,2}, \dots, a_{i,i} \left(0\leqq a_{i,j}\leqq 1\right)，其中，a_{i,j} 表示三角形中第 i 行第 j 个元素。

输出描述:

\hspace{15pt}一个整数，表示字符串 b 为回文串的路径总数。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

复制 
3
1
0 0
1 1 1

输出

复制 
4
示例2

输入

复制 
1
1

输出

复制 
1