现在有一个长度为 的随机排列，求它的最长上升子序列长度的期望。
为了避免精度误差，你只需要输出答案模 的余数。
4900: [BJWC2018] 最长上升子序列
Memory Limit：512 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：1
Solved：1
Description
Input
输入只包含一个正整数 。
Output
输出只包含一个非负整数，表示答案模 的余数。
可以证明，答案一定为有理数，设其为 （ 为互质的整数），你输出的整数为 ，则你需要保证 且 与 模 同余。
Sample Input Copy
2
Sample Output Copy
499122178
HINT
【样例 #2 说明】
这是 。
【数据规模和约定】
对于 的数据，。
共有 25 组数据，对于第 组数据（），。