#P17992. Palindromes

Palindromes

Palindromes

题目描述

有一个未知的长度为 NN 的字符串,字符集为 {a,b}\{\texttt{a},\texttt{b}\}。你知道它长度为 a1,a2,…,ana_1,a_2,\ldots,a_n 的前缀都是回文串,即从左往右读与从右往左读相同。

求符合这些条件的字符串数量,对 mm 取模。

除列出的前缀外,字符串的其他前缀也可以是回文串。

输入格式

第一行三个整数 N,n,mN,n,m。

第二行 nn 个严格递增的整数 a1,…,ana_1,\ldots,a_n,表示要求为回文串的前缀长度。

输出格式

输出一个非负整数,表示答案模 mm 的值。

数据范围

1≤N≤10181\le N\le10^{18},1≤n≤5000001\le n\le500000,2≤m≤1092\le m\le10^9,1≤a1<⋯<an≤N1\le a_1<\cdots<a_n\le N。mm 不保证为质数。

样例输入

10 3 100
2 5 9

样例输出

8