题目背景

观测站日复一日地记录着一路上的整数读数。记录仪断电过几回，纸带上有若干段是空白，只剩下一些零散的时刻还留着笔迹。

题目描述

记录仪留下了 $n$ 个时刻的读数。其中一些时刻的读数已经损坏，用 ? 表示；其余时刻的读数是保留下来的整数。

已知这份记录的物理规律：相邻两个时刻的读数相差不超过 $1$（可以上升 $1$、下降 $1$ 或者保持不变）。读数本身可以是任意整数，允许为负。

请统计有多少种可能的原始读数序列，使得所有受损的时刻都被填上整数，保留下来的读数与给定值完全一致，并且整份记录满足上述规律。答案对 $998244353$ 取模。

保证第 $1$ 个时刻与第 $n$ 个时刻的读数没有损坏。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个记号，以空格分隔，每个记号要么是一个整数，要么是一个 ?。

输出格式

一行一个整数，表示可能的记录份数对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

1
5

输出 #1

1

输入输出样例 #2

输入 #2

2
3 4

输出 #2

1

输入输出样例 #3

输入 #3

2
3 7

输出 #3

0

输入输出样例 #4

输入 #4

3
1 ? 1

输出 #4

3

说明

样例解释

样例 1 只有一个时刻，读数已经确定，方案数为 $1$。

样例 2 两段读数相差 $1$，符合规律，方案数为 $1$。

样例 3 两段读数相差 $4$，超过相邻读数允许的差距，无解，方案数为 $0$。

样例 4 中间时刻的读数可以是 $-1$、$0$、$1$，这三种取值都能使相邻两处差值不超过 $1$，所以方案数为 $3$。

数据范围

• 对于 $30\%$ 的数据，$n \le 20$；
• 对于 $60\%$ 的数据，$n \le 5000$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，保留下来的读数绝对值不超过 $10^9$。