对于一个由有限个非负整数组成的数列 X，我们定义 mex(X) 为数列中不包含的最小非负整数。例如，mex((0,0,1,3))=2，mex((1))=0，mex(())=0。

给定一个长度为 N 的数列 S=(S₁,…,S_N)，其中每个元素均为 0 或 1。

要求计算满足以下条件的长度为 N 的数列 A=(A₁,A₂,…,A_N)的数量，并对结果取模 998244353。

0≤Ai≤M。

对于所有 i(1≤i≤N)，如果 Si=1，则 Ai=mex((A1,A2,…,Ai−1))；如果 Si=0，则 Ai≠mex((A1,A2,…,Ai−1))。

样例解释 #1

满足条件的数列有以下 4 个：

• (0,0,0,1)
  

• (0,0,2,1)
  

• (0,2,0,1)
  

• (0,2,2,1)