| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 256 MB | 17 | 8 | 7 | 53.846% |
For a permutation $p$, denote the number of inversions in it as $\mathit{inv}(p)$. An inversion is a pair of indices $1 \le i < j \le |p|$ such that $p_i > p_j$.
Given are integers $n$ and $k$. Find the sum of $\mathit{inv}(p)^k$ over all permutations $p$ of length $n$. As the answer can be very large, find it modulo $998\,244\,353$.
The only line contains two integers, $n$ and $k$ ($1 \le n \le 10^{18}$, $1 \le k \le 1000$).
Print the answer modulo $998\,244\,353$.
3 2
19
5 3
22500
In the first example:
In permutation $(1,2,3)$, there are $0$ inversions.
In $(1,3,2)$, there is $1$ inversion.
In $(2,1,3)$, there is $1$ inversion.
In $(2,3,1)$, there are $2$ inversions.
In $(3,1,2)$, there are $2$ inversions.
In $(3,2,1)$, there are $3$ inversions.
The answer is: $0^2 + 1^2 + 1^2 + 2^2 + 2^2 + 3^2 = 19$.