在 Never 共和国有 $n$ 座城市和 $n-1$ 条道路。城市编号为 $1$ 到 $n$。道路编号为 $1$ 到 $n-1$，第 $i$ 条道路连接城市 $i$ 和 $i+1$。每条道路都可以双向通行。城市 $u$ 和 $v$ 之间的距离定义为从 $u$ 到 $v$ 所需经过的最少道路数量，即 $d(u, v) = |u - v|$。

有 $k$ 位朋友想要聚会。第 $i$ 位朋友住在城市 $a_i$。为了聚会，朋友们会选择一个城市 $v$，使得 $\sum_{i=1}^{k} d(v, a_i)$ 最小。如果存在多个这样的城市，他们会选择其中编号最小的一个。

不幸的是，你只知道朋友的数量，而不知道他们居住的城市。每位朋友可能住在 $n$ 座城市中的任意一座；因此，总共有 $n^k$ 种可能的情况。你需要计算在所有 $n^k$ 种情况中，朋友们选择的城市编号之和。输出该和对 $998\,244\,353$ 取模的结果。

输入格式

输入仅一行，包含两个整数 $n$ 和 $k$，分别表示城市数量和朋友数量（$2 \le n, k \le 10^6$）。

输出格式

输出在所有 $n^k$ 种情况中，朋友们选择的城市编号之和，对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

3 2

样例输出 1

14

样例输入 2

5 3

样例输出 2

375

说明

在第一个样例中，有 3 座城市和 2 位朋友，共有 $3^2 = 9$ 种情况需要考虑。如果其中任意一位朋友住在城市 1，朋友们会选择城市 1，这种情况共有 5 种。否则，如果其中任意一位朋友住在城市 2，朋友们会选择城市 2，这种情况共有 3 种。在剩下的情况中，如果两位朋友都住在城市 3，他们会选择城市 3，这种情况有 1 种。总和为 $5 \cdot 1 + 3 \cdot 2 + 1 \cdot 3 = 14$。