#MX95. 好的序列
好的序列
时间限制:2000ms
空间限制:1024MB
题目描述
给定长度为 的正整数序列 。
一个长度为 的序列 是好的,当且仅当对于 ,都有 。
求解有多少个长度为 的好的正整数序列 ,满足对于 都有 ,答案对 取模。
输入格式
第一行包含 个正整数 。
第二行给定长度为 的正整数序列 。
输出格式
输出一行,输出 个整数,表示最终答案,答案对 取模。
样例 1 输入
3
2 2 2
样例 1 输出
2
样例解释
满足要求的序列有 ,。
样例 2 输入
10
2 3 4 5 9 8 7 1 2 3
样例 2 输出
28722
样例 3 输入
50
98 123 123 42 55 67 82 10 23 20 98 123 123 42 55 67 81 10 23 20 98 123 123 42 55 67 89 10 23 20 98 123 124 42 55 67 89 10 23 20 98 123 123 42 55 67 89 10 23 20
样例 3 输出
149787148
评测数据规模
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于所有测评数据,。