题目描述
聪明的 Cirno 开始学习计算,于是她很开心的算出了从 1 一直加到 n。
得到了一个 n 项的数列 : {an = 1+2+3+4+...+n}
为了验证自己算是否算错,她需要以某种规律从数列里取出两个元素 v1,v2(元素可以相同),并等概率的选出整数 a∈[1,v1],b∈[1,v2] 判断哪个比较大.
所以她需要你来计算 a>b 的概率。
某种规律:
选到数列第 i 个元素的概率是:
n=1∑nanai=n(n+1)(n+2)3i×(i+1)输入格式
输入一个正整数 n。
输出格式
输出在模 998244353 意义下的概率。
提示
对于前 5% 的数据 n=3;
对于前 15% 的数据 n≤100;
对于前 30% 的数据 n≤5000;
对于前 55% 的数据 n≤107;
对于前 95% 的数据 1≤n≤1018;
对于最后 5% 的数据 n=0 表示 正无穷;
对于 100% 的数据 n 不为 998244353 的倍数。