题目描述

本题题解已发表至 讨论区

“我与op不共戴天！！！”，这是我们学校著名的xx组组长支梦祥说出的经典名言。

原来是zmx的室友zhn是个op，于是zmx偷偷去修改了原神抽奖代码，把单发抽奖抽出水神的概率调成了p/10000，顺便把保底机制和十连取消了。

于是抽奖变成了只能单抽和没有保底的抽奖制度。

zhn想要抽水神，但是需要原石，所以先去肝原石，才能去抽奖。

第一天很快就肝出了一抽的原石，于是在他去抽，发现没中，没办法只能再去肝原石。

但是zhn的肝也是有极限的，每次肝出一抽的原石都需要花费比上一次肝出一抽的原石的天数多一天。

也就是说，当去肝第i抽原石时，需要花费的天数是第i-1抽的天数+1。

每当zhn肝出一抽原石时，当天他就会去抽一发，中了水神就不会再肝了。

于是他想知道，他大概需要肝多少天才能抽中水神。

输出结果请对998244353取模。

可以证明答案可以用分数 p/q 表示，其中 p 和 q 都是正整数且互质。如果存在一个小于 998244353 的非负整数 r，满足 q * r mod (998244353) = p，我们就称这个整数 r 为 p/q modulo 998244353 的结果。

$\frac{1}{b} 在取模m意义下的值等于b^{m-2} mod$ $m$

输入描述

第一行为p，表示zmx改成的概率p/10000

$1 \leq p \leq 10000$

输出描述

输出一个数，表示需要多少天才能抽中水神。

示例 1

输入

10000

输出

1

说明

第一天肝出了一抽原石，直接一发入魂！！！

备注

注意：题目只是表示规则，并不代表第一抽一定不中。