Ranran 有一个排列 $p$。 他想要计算 $p$ 的每一个前缀的中位数。 $n$ 个数的中位数是第 $\lceil n/2 \rceil$ 小的元素。 例如，$\{1, 2, 3, 4, 5, 6\}$ 的中位数是 $3$，$\{1, 2, 4, 8, 16\}$ 的中位数是 $4$。 由于输入可能很大，该排列由以下代码生成： $a_i = (a_{i-1} * 998244353 + 10^9 + 7) \pmod{10^9 + 9}$，$p_i = i$ 然后对于 $i$ 从 $1$ 到 $n$，执行 $\text{swap}(p_i, p_{(a_i \pmod i) + 1})$ 现在我们得到了排列 $p$。

输入格式

第一行包含两个整数 $n(1 \le n \le 10^7)$ 和 $a_0(0 \le a_0 < 10^9 + 9)$。

输出格式

令 $ans_i$ 为前缀 $p_{1 \dots i}$ 的答案，输出 $\sum (ans_i * 19^i) \pmod{998244353}$。

样例

样例输入 1

5 0

样例输出 1

7703113

样例输入 2

5 1

样例输出 2

7840977