It is known that any irrational number d greater than 1 can be represented as infinite continued fraction:

Here a_i are positive integers. A convergent fraction of order k of number d is a rational number [a₀, a₁, …, a_k], that is a representation of d as a continued fraction, truncated to the first k + 1 elements.

Given an integer x, find numerator and denominator of convergent continued fraction of order k of the square root of x.

The only input line contains integers x and k (2 ≤ x ≤ 10⁶; 0 ≤ k ≤ 10⁹). x is not a perfect square.

Output the value of the convergent continued fraction of order k of the square root of x as an irreducible fraction. Output numerator and denominator modulo 10⁹ + 7.