There are two positive integers $n$ and $m$.
We consider all integer sequences of length $n$ where each element is in $[1, m]$. For each integer sequence, let $\text{lcm}$ be the least common multiple of the elements in the sequence, and $\text{gcd}$ be the greatest common divisor of the elements in the sequence. We wish to find $\text{lcm}^{\text{gcd}}$. You need to calculate the product of $\text{lcm}^{\text{gcd}}$ for all such integer sequences modulo $998244353$.
That is, we need to calculate: $$\left( \prod_{x_1, x_2, \dots, x_n \in [1, m]} \text{lcm}(x_1, x_2, \dots, x_n)^{\text{gcd}(x_1, x_2, \dots, x_n)} \right) \pmod{998244353}$$
Input
A single line containing two positive integers $n, m$.
Output
Output the value of: $$\left( \prod_{x_1, x_2, \dots, x_n \in [1, m]} \text{lcm}(x_1, x_2, \dots, x_n)^{\text{gcd}(x_1, x_2, \dots, x_n)} \right) \pmod{998244353}$$
Examples
Input 1
1 3
Output 1
108
Input 2
2 4
Output 2
629124429
Input 3
5 5
Output 3
355944288
Subtasks
- Subtask 1 (10pts): $n, m \le 5$.
- Subtask 2 (20pts): $n, m \le 50$.
- Subtask 3 (10pts): $n, m \le 500$.
- Subtask 4 (20pts): $n, m \le 50000$.
- Subtask 5 (20pts): $n, m \le 200000$.
- Subtask 6 (20pts): $n \le 10^8, m \le 200000$.