29093번 - Любимые числа 다국어

문제

--- Какое у вас любимое число, мейстер Эйемон? --- спросил Сэм.

--- Конечно, 2068965517241379310344827586, --- ответил мейстер.

--- Почему?

--- Это первое число, такое, что оно заканчивается на цифру 6, и если перенести эту цифру в начало, оно увеличится ровно в 3 раза! Нахождение всех таких чисел было задачей на моем вступительном экзамене в академию. Если ты хочешь поступить в академию, ты должен быть достаточно подготовлен. Сумеешь ли ты найти $k$-е по порядку число с таким свойством? Дабы не утруждать cебя, посчитай только остаток от деления этого числа на 10ドル^9+7$.

입력

В первой и единственной строке входного файла записано одно целое число $k$ (1ドル \le k \le 10^9$) --- порядковый номер искомого числа, которое Вам нужно найти.

출력

В единственной строке выходного файла выведите остаток от деления искомого числа на 10ドル^9+7$.

제한

힌트