#P18097. Sort
Sort
Sort
题目描述
给定长度为 的排列 。每次操作独立地等概率选择整数 ,分别将 与 升序排序。当 时,第二段为空,相当于将整个排列排序。
求排列首次变成完全升序所需的操作次数的期望,对 取模。初始排列已经升序时,操作次数为 。有理数 在模意义下表示为 。
输入格式
第一行一个整数 。每组数据先输入 ,下一行输入 。
输出格式
每组数据输出一行,一个整数,表示期望的模值。
数据范围
,; 是 的排列。一个输入文件中所有 之和不超过 。
样例 1
输入
3
3
3 1 2
2
2 1
5
3 2 5 1 4
输出
748683267
2
670695427