#H1090. 无聊的集合

无聊的集合

题目描述

小K很无聊,对于集合 T={a1,a2,,an1,an}(a1a2an1an) T=\{a_1,a_2,\dots,a_{n-1},a_n\}(a_1\ge a_2\ge\dots\ge a_{n-1}\ge a_n) ,定义权值 P(T)=i=1nai×(1)i1 P(T)=\sum_{i=1}^n a_i\times (-1)^{i-1}

又定义 S1(T)=P(T) S_1(T)=P(T) Si(T)=RTSi1(R) S_i(T)=\sum_{R\in T}S_{i-1}(R)

给定 n,m,p n,m,p ,他想知道 Sn({m,m1,m2,,2,1})modp S_n(\{m,m-1,m-2,\dots,2,1\})\mod p

输入

一行 n,m,pn,m,p 三个数。

输出

一个整数 Sn({m,m1,m2,,2,1})modp S_n(\{m,m-1,m-2,\dots,2,1\})\mod p

样例

2 3 998244353
12
1 66666 100000007
33333
48324 98323 100000007
73978329

数据范围

1n,m105,108p109,p 1\le n,m\le 10^5,10^8\le p\le 10^9,p 为质数。

test# n m score
11 =1=1 105\le10^5 55
22 =2=2 1010
33 100\le100 2525
44 105\le10^5 100\le100
55 105\le10^5 3535