武义寺

题号：NC229190
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给，小和尚叫扶弱呱。老和尚说“从前有个寺庙，名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给，小和尚叫扶弱呱……”
有一天，扶弱给在潜心研究排列。他在脑中随机一个排列的时候，脑海里冒出了这样一个问题：
对于一个排列 ${p= \{ 1,2,...,n\}}$ ，记 $\text{val}(p)$ 等于最小的 ${i}$ 满足 ${i}> a_i$ ，如不存在则 $\text{val}(p)=n+1$ 。

可是 $\text{val}(p)$ 的期望值是多少呢？显然，扶弱给没学过编程，需要你来帮帮他。

本场比赛大样例：https://uploadfiles.nowcoder.com/files/20211016/%E5%A4%A7%E6%A0%B7%E4%BE%8B.zip

输入描述:

输入一个数  。

输出描述:

输出  的期望值，答案对  取模。

示例1

输入

复制

输出

复制

499122179

说明

对于排列  ，；对于排列 ，。因此期望值为 。

备注:

对于  的数据， ；
对于  的数据， ；
对于  的数据， ；
对于  的数据， 。