#575. 合唱比赛

合唱比赛

样例下载

题目描述

Farmer John 有 NN 头奶牛,编号为 11 ~ NN,编号为 ii 的奶牛的身高为 HiH_i。任意两头奶牛的身高互不相同。

这一天,奶牛们全部去参加合唱比赛。它们已经排成一队入场了。

John 在场外等待。他想等比赛结束后,奶牛们仍然按入场顺序排队返回。

但是 John 已经忘记了奶牛们的入场顺序,他只记得入场队列中恰好存在 MM 对逆序奶牛。

所谓逆序奶牛,是指对于两头奶牛 ii 和 jj,如果奶牛 ii 比奶牛 jj 先入场,但是奶牛 ii 的身高大于奶牛 jj 的身高,则称奶牛 ii 和奶牛 jj 是一对逆序奶牛。

问:比赛入场时,奶牛们有多少种可能的排队方案?答案可能很大,你需要将其 mod PP 后输出。

输入格式

第一行,包含三个整数 N,M,PN, M, P。

第二行,包含 NN 个整数 HiH_i

输出格式

一个整数,表示答案 mod PP。

样例输入

3 1 5
1 3 5

样例输出

2

样例解释

入场队列有 2 种可能:

1, 5, 3

3, 1, 5

数据范围

对于 30% 的数据,N,M≤20N, M ≤ 20;

对于 100% 的数据,N,M≤1000,1≤P,Hi≤109N, M ≤ 1000, 1 ≤ P, H_i ≤ 10^9,数据保证奶牛的身高两两不同。