对于一个排列 $p$，记其逆序对数量为 $inv(p)$。逆序对是指满足 $1 \le i < j \le |p|$ 且 $p_i > p_j$ 的下标对 $(i, j)$。

给定整数 $n$ 和 $k$。求所有长度为 $n$ 的排列 $p$ 的 $inv(p)^k$ 之和。由于答案可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

输入格式

仅一行，包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^{18}$, $1 \le k \le 1000$)。

输出格式

输出答案对 $998\,244\,353$ 取模的结果。

样例

输入 1

3 2

输出 1

19

输入 2

5 3

输出 2

22500

说明

在第一个样例中： 排列 $(1, 2, 3)$ 有 $0$ 个逆序对。 $(1, 3, 2)$ 有 $1$ 个逆序对。 $(2, 1, 3)$ 有 $1$ 个逆序对。 $(2, 3, 1)$ 有 $2$ 个逆序对。 $(3, 1, 2)$ 有 $2$ 个逆序对。 $(3, 2, 1)$ 有 $3$ 个逆序对。 答案为：$0^2 + 1^2 + 1^2 + 2^2 + 2^2 + 3^2 = 19$。