#575. 合唱比赛
合唱比赛
题目描述
Farmer John 有 头奶牛,编号为 ~ ,编号为 的奶牛的身高为 。任意两头奶牛的身高互不相同。
这一天,奶牛们全部去参加合唱比赛。它们已经排成一队入场了。
John 在场外等待。他想等比赛结束后,奶牛们仍然按入场顺序排队返回。
但是 John 已经忘记了奶牛们的入场顺序,他只记得入场队列中恰好存在 对逆序奶牛。
所谓逆序奶牛,是指对于两头奶牛 和 ,如果奶牛 比奶牛 先入场,但是奶牛 的身高大于奶牛 的身高,则称奶牛 和奶牛 是一对逆序奶牛。
问:比赛入场时,奶牛们有多少种可能的排队方案?答案可能很大,你需要将其 mod 后输出。
输入格式
第一行,包含三个整数 。
第二行,包含 个整数
输出格式
一个整数,表示答案 mod 。
样例输入
3 1 5
1 3 5
样例输出
2
样例解释
入场队列有 2 种可能:
1, 5, 3
3, 1, 5
数据范围
对于 30% 的数据,;
对于 100% 的数据,,数据保证奶牛的身高两两不同。