ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Contest is over

E. Continued Fraction

Time limit: 0.5 second
Memory limit: 64 MB
It is known that any irrational number d greater than 1 can be represented as infinite continued fraction: Here ai are positive integers. A convergent fraction of order k of number d is a rational number [a0, a1, …, ak], 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 ≤ 106; 0 ≤ k ≤ 109). 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 109 + 7.

Sample

inputoutput
2 3
17/12
Problem Source: Tavrida NU Akai Contest. Petrozavodsk Summer Session, August 2010
To submit the solution for this problem go to the Problem set: 1814. Continued Fraction