⭐我喜欢海棠花不眠 可惜一切都来不及了... Bingbong 拿到一个由数字 和 组成的三角形，一共有 行，第 行有 个数字。我们使用 表示从上往下数第 行和从左往右数第 列的位置，使用 代表这个单元格中的数字。 Bingbong 初始时位于 ，她每次移动会选择移动到 或者 ，每到一个位置会得到该位置的元素值，记作 。 最终移动到第 行时，共得到了 个元素，通过拼接后，我们记作 ，即字符串 。 现在请你求出到达第 行后，有多少条路径满足字符串 是一个回文串。由于答案可能很大，请将答案对 取模后输出。 一个字符串被称作回文串，当且仅当这个字符串从左往右读和从右往左读是相同的。

输入描述:

第一行输入一个整数 ，表示行数。 此后 行，第 行输入 个整数 ，其中， 表示三角形中第 行第 个元素。

输出描述:

一个整数，表示字符串 为回文串的路径总数。由于答案可能很大，请将答案对 取模后输出。