#P9639. 武义寺

    ID: 6255 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 6 上传者: 标签>CF1900普及+/提高-尾和公式乘法原理排列数计算快速幂模逆元

武义寺

题目描述

从前有个寺庙,名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给,小和尚叫扶弱呱。老和尚说「从前有个寺庙,名为武义寺。庙里有个老和尚和小和尚。老和尚叫扶弱给,小和尚叫扶弱呱……」

有一天,扶弱给在潜心研究排列。他在脑中随机一个排列的时候,脑海里冒出了这样一个问题: 对于一个排列 p={1,2,...,n}p = \{1,2, . . . , n\} ​​​​​,记 val(p)\text{val}(p)​​​​​ 等于最小的 ii​​​​ 满足 i>pii > p_i​​​​ ,如不存在则 val(p)=n+1\text{val}(p) = n + 1​​​​ 。 可是 val(p)\text{val}(p)​​​​ 的期望值是多少呢?显然,扶弱给没学过编程,需要你来帮帮他。

输入格式

输入一个数 nn。

输出格式

输出 val(p)\text{val}(p)​ 的期望值,答案对 998244353998244353 取模。

样例

2
499122179

对于排列 p=1,2p = {1,2},val(p)=3\text{val}(p) = 3;

对于排列 p=2,1p = {2,1},val(p)=2\text{val}(p) = 2。因此期望值为 25\frac{2}{5} 。

数据范围

  • 对于 30%30\% 的数据,1≤nle51 \le n le 5;
  • 对于 50%50\% 的数据,1≤n≤201 \le n \le 20;
  • 对于 80%80\% 的数据,1≤n≤1051 \le n \le 10^5;
  • 对于 100%100\% 的数据,1≤n≤1061 \le n \le 10^6 。