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*_{0}, *a*_{1}, …, *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*.

### Input

The only input line contains integers *x* and *k*
(2 ≤ *x* ≤ 10^{6}; 0 ≤ *k* ≤ 10^{9}). *x* is not a perfect square.

### Output

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^{9} + 7.

### Sample

**Problem Source: **Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010