Migrated from Lutece 811 GCD

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Calculate

In mathematics, the greatest common divisor (GCD), also known as the greatest common factor (GCF), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of $8$ and $12$ is $4$.

Input

The input contains two integers $N$, $K$, $(1\leq N\leq 10^{10}, 1\leq K\leq 5)$,

Output

Output the answer module $10^9 + 7$.

Samples

2 2

7

Note

Data Repair by xiper

Resources

The 12th UESTC Programming Contest Final