No.3551 Regions by Random Points 2
Problem Statement
Perform the following operation $N$ times: place $2$ points independently and uniformly at random on the circumference of a circle, and connect them with a line segment.
Find the expected value, $\mathrm{mod}$ $998244353$, of the number of regions into which the interior of the circle is divided by these $N$ line segments.
Definition of expected value $\mathrm{mod}$ $998244353$ (click to open)
Under the constraints of this problem, the expected value to be found is always a rational number, and it is guaranteed that it can be expressed as $\frac{y}{x}$ using an integer $x ~ \big(x \not\equiv 0 ~ (\mathrm{mod} ~ 998244353)\big)$ and an integer $y$.
In this case, there exists a unique integer $z$ between $0$ inclusive and $998244353$ exclusive satisfying $xz \equiv y$ $(\mathrm{mod}$ $998244353)$, so output that value.
Constraints
- $1 \le N \le 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format.
$N$
Output
Output the answer.
Sample
Sample 1
Input
8
Output
332748136When $N=8$, the answer is $\dfrac{55}{3}$.
Sample 2
Input
1000000000
Output
952678484
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ