瓜子

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

QQ 买了 nn 粒瓜子。

Description

QQ 每次都会从这堆瓜子中挑出一粒,他每次吃完一粒瓜子后,就会得到两瓣瓜子壳,他会把瓜子壳也丢进瓜子堆里面去。

如果他拿到了自己之前吃瓜子留下的瓜子壳,他就会把拿到的瓜子壳丢掉,否则就吃掉拿到的瓜子并且把瓜子壳丢进去。

现在设每次小 QQ 拿到每一粒瓜子或者是瓜子壳的概率是均等的,问 小L 期望多少次能够把瓜子拿完。

Format

Input

一行一个正整数 nn

Output

一行一个整数表示结果对于 998244353 取模的结果。

Samples

2
3

Limitation

n=2n=2 的时候,这个时候 小L 第一次拿到的肯定是瓜子,然后现在瓜子堆里面有 11 粒瓜子,22 个瓜子壳。接下来他有 13\frac13 的概率拿到瓜子,有 23×13\frac23×\frac13 的概率第一次拿到瓜子壳,第二次拿到瓜子。还有 23×12=13\frac23×\frac12=\frac13 的概率再拿两次都拿到瓜子壳,最后拿到瓜子。

所以期望的次数:2×13+3×13+4×13=32×\frac13+3×\frac13+4×\frac13=3

对于 100%100\% 的数据满足 n2×103n≤2×10^3

菜就多练

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
23
Start at
2024-3-2 19:00
End at
1970-1-1 8:00
Duration
-474827 hour(s)
Host
Partic.
0