GCD Graph

A GCD Graph with $N$ vertices is defined as follows:

• The vertices of the graph are labelled with the numbers $1$ through $N$.
• For all $1\leq i,j\leq N$, if $\gcd(i, j)=1$, then an edge exists between vertex $i$ and vertex $j$.

Starting from any vertex of this graph and moving along edges a total of $K$ times is called a walk. Given the number of vertices $N$ and the number of moves $K$, find the total number of walks that exist in the GCD Graph. Since the answer can become extremely large, output it modulo $10^9+7$.

The first line contains the integers $N$ and $K$, separated by a space. $(1\leq N\leq10^6,0\leq K\leq500)$

Print the answer to the problem.