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