Given $n$ and $d$, calculate

$$\mathrm{ans} = \sum_{0 \leq x,y,z < n} (x \oplus y \oplus z)^d \bmod{998\,244\,353}$$

Input

Two integers $n$ and $d$.

Output

Output the integer $\mathrm{ans}$.

Examples

Input 1

10 3

Output 1

718116

Subtasks

For subtask 1 ($10\%$): $0 < n \leq 300$, $d \leq 3$.

For subtask 2 ($10\%$): $0 < n \leq 5\,000$, $d \leq 3$.

For subtask 3 ($20\%$): $0 < n \leq 10^5$, $d \leq 3$.

For subtask 4 ($20\%$): $0 < n \leq 2^{30}$, $d \leq 3$.

For subtask 5 ($20\%$): $0 < n \leq 2^{30}$, $d \leq 10$.

For subtask 6 ($20\%$): $0 < n \leq 2^{30}$, $d \leq 10^5$.