No.3479 Regions by Random Points
Problem Statement
$N$ points are placed independently and uniformly at random inside a square.
When all pairs of these $N$ points are connected by line segments, find the expected value, $\mathrm{mod}$ $998244353$, of the number of regions into which the interior of the square is divided by those segments.
Definition of expected value $\mathrm{mod}$ $998244353$ (click to open)
Under the constraints of this problem, it is guaranteed that the expected value to be found is always a rational number and 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$ and less than $998244353$ satisfying $xz \equiv y$ $(\mathrm{mod}$ $998244353)$, so report that value as your answer.
Constraints
- All inputs are integers.
- $1 \le N \le 10^9$
Input
The input is given from standard input in the following format.
$N$
Output
Output the answer.
Sample
Sample 1
Input
4
Output
526851191
When $N=4$, the answer is $\dfrac{169}{36}$.
Sample 2
Input
1000000000
Output
751221712
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ぽえ