一共有n个三体人，所有三体人的战斗力可以由一个数列 a 1 , a 2 , … … , a n a 1​,a 2​,……,a n​表示，由于三体人长期生活在三体运动的影响下，导致他们有一个致命弱点：如果有三个三体人的战斗力之和为偶数，那么他们会变得非常脆弱！聪明的小桃立刻察觉到，如果可以将三体人的战斗力分割出一个子序列，使得子序列任意相邻 3 3个数的和都是偶数，那么就可以轻松击破这部分三体人。

现在小桃想请你帮她计算，按照她的计划，可以分割出多少种子序列满足上述条件，结果对 998244353 998244353 取模。

输入格式 共两行，第一行一个整数一个整数 n n ,表示一共有多少三体人

第二行n个整数，表示三体人的战斗力

输出格式 输出一个整数，分割子序列的方案数，答案对 998244353 998244353 取模