24668번 - Inversions 다국어

문제

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円$.

제한

힌트

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$.