ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Tavrida NU Akai contest. Petrozavodsk training camp. Summer 2010

About     Problems     Submit solution     Judge status     Standings
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:
Problem illustration
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