C. Lucyyx Never Clear
time limit per test
10 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

We define the function $$$F(N, M)$$$ to be the number of ordered pairs of integers $$$(a, b)$$$ such that $$$1 \leq a \leq N$$$, $$$1 \leq b \leq M$$$, and $$$\gcd \left( \frac{a}{\gcd(a, b)}, b \right) = \gcd(a, b)$$$.

You are given that $$$F(3, 3) = 7$$$, $$$F(10, 10^3) = 6947$$$, and $$$F(10^5, 10^3) = 69278063$$$.

Find $$$F(n, m)$$$ modulo $$$998\,244\,353$$$.

Input

The first and only line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 10^{10}$$$) — the values for which you must calculate $$$F(n, m)$$$.

Output

Output a single integer — the value $$$F(n, m)$$$ modulo $$$998\,244\,353$$$.

Examples
Input
3 3
Output
7
Input
10 1000
Output
6947
Input
100000 1000
Output
69278063
Note

In the first test case, we have that $$$\gcd \left( \frac{3}{\gcd(3, 1)}, 1 \right) = 1 = \gcd(3, 1)$$$, so $$$(3, 1)$$$ is counted as a valid ordered pair. We also have that $$$\gcd \left( \frac{2}{\gcd(2, 2)}, 2 \right) = 1 \neq 2 = \gcd(2, 2)$$$, so $$$(2, 2)$$$ is not counted as a valid ordered pair. The $$$7$$$ valid ordered pairs are $$$(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1),$$$ and $$$(3, 2)$$$.