Известно, что любое иррациональное число d большее единицы можно представить в виде бесконечной цепной дроби:

Здесь a_i — это положительные целые числа. Подходящей цепной дробью порядка k для числа d называется рациональное число [a₀, a₁, …, a_k], полученное рассмотрением первых k + 1 элементов цепной дроби для d.

Требуется по данному целому числу x вычислить числитель и знаменатель подходящей цепной дроби порядка k для квадратного корня из x.

В единственной строке записаны целые числа x и k (2 ≤ x ≤ 10⁶; 0 ≤ k ≤ 10⁹). Число x не является полным квадратом.

Выведите значение подходящей цепной дроби порядка k для квадратного корня из x в виде несократимой дроби. Числитель и знаменатель требуется выводить по модулю 10⁹ + 7.