#5298. [Cqoi2018]交错序列

我们称一个仅由0、1构成的序列为"交错序列"，当且仅当序列中没有相邻的1（可以有相邻的0）。例如，000，001

，101，都是交错序列，而110则不是。对于一个长度为n的交错序列，统计其中0和1出现的次数，分别记为x和y。

给定参数a、b，定义一个交错序列的特征值为x^ay^b。注意这里规定任何整数的0次幂都等于1（包括0^0=1）。

显然长度为n的交错序列可能有多个。我们想要知道，所有长度为n的交错序列的特征值的和，除以m的余数。(m是

一个给定的质数)例如，全部长度为3的交错串为：000、001、010、100、101。

当a=1，b=2时，可计算3¹x0²+2¹x1²+2¹x1²+2¹x1²+1¹x2²=10