The Holmes children are fighting over who amongst them is the cleverest.

Mycroft asked Sherlock and Eurus to find value of f(n), where f(1) = 1 and for n ≥ 2, f(n) is the number of distinct ordered positive integer pairs (x, y) that satisfy x + y = n and gcd(x, y) = 1. The integer gcd(a, b) is the greatest common divisor of a and b.

Sherlock said that solving this was child's play and asked Mycroft to instead get the value of . Summation is done over all positive integers d that divide n.

Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.

She defined a k-composite function F_k(n) recursively as follows:

She wants them to tell the value of F_k(n) modulo 1000000007.

A single line of input contains two space separated integers n (1 ≤ n ≤ 10¹²) and k (1 ≤ k ≤ 10¹²) indicating that Eurus asks Sherlock and Mycroft to find the value of F_k(n) modulo 1000000007.

Output a single integer — the value of F_k(n) modulo 1000000007.