In the silent world, I open my hands to touch you, Wanting to break free from this muddy, heavy gravity. I breathe hard in fear, Expecting a miracle that cannot happen. I close my eyes, Not seeing the deviating heart rate. Helpless efforts, gradually giving up. In my incomplete heart, I am crying and shouting. Now, I am still scattered on the lunar surface, Waiting for time to pass, To settle. Where am I? — "Lunar Eccentricity"

Xiao L has finally seen the far side of the moon, but it is desolate, cold, and dull.

He wants to paint it a passionate pink. To do this, he consulted a math book and found a function $f_t(n)=2^{\omega(n)}n^t$, which he will use to determine the coloring process.

Here, $\omega(n)$ is the number of distinct prime factors of $n$. For example, $\omega(1)=0, \omega(2)=1, \omega(8)=1, \omega(6)=2$.

Xiao L first divided the area into $n \times n$ regions, pouring a different amount of pink paint into each. Specifically, he pours $f_t(\gcd(i,j)) f_t(\operatorname{lcm}(i,j))$ buckets of paint into the region at row $i$ and column $j$.

However, he no longer has the energy to calculate this, so please tell him the total number of buckets of pink paint required.

Furthermore, if the answer above is denoted as $F_t(n)$, Xiao L will give you an integer $m \in \{0,1\}$:

• If $m=0$, please output $F_0(n)$.
• If $m=1$, please output $F_0(n)$ and $F_1(n)$.

Since the answer may be very large, please output the result modulo $10^9+7$.

Input

A single line containing two integers $n$ and $m$.

Output

$m+1$ integers, with meanings as described above.

Examples

Input 1

3 1

Output 1

25 121

Input 2

1000 0

Output 2

24870169

Input 3

10000000000 0

Output 3

213223517

Input 4

100000000000000 1

Output 4

8177545 370603117

Subtasks

• Subtask 1 (3 points): $1 \leq n \leq 5000, m \in \{0,1\}$.
• Subtask 2 (3 points): $1 \leq n \leq 10^7, m \in \{0,1\}$.
• Subtask 3 (8 points): $1 \leq n \leq 10^{10}, m=0$.
• Subtask 4 (8 points): $1 \leq n \leq 10^{10}, m \in \{0,1\}$.
• Subtask 5 (8 points): $1 \leq n \leq 10^{12}, m \in \{0,1\}$.
• Subtask 6 (10 points): $1 \leq n \leq 10^{13}, m \in \{0,1\}$.
• Subtask 7 (13 points): $1 \leq n \leq 10^{14}, m=0$.
• Subtask 8 (14 points): $1 \leq n \leq 10^{14}, m \in \{0,1\}$.
• Subtask 9 (16 points): $1 \leq n \leq 10^{16}, m=0$.
• Subtask 10 (17 points): $1 \leq n \leq 10^{15}, m \in \{0,1\}$.

Please note the differences in the data ranges for Subtask 9 and Subtask 10.