Xanoy minorasi $XIX$ asrning mashhur jumboqlaridan biridir. Uchta novda beriladi, ulardan biri $n$ ta halqaga ega bo'lib, vazifa halqalarni birisidan ikkinchisiga o'tkazishdir. Bir amalni o'zida faqat bitta halqani olib boshqasiga qo'yishga ruxsat beriladi va siz katta halqani kichkisaniga qo'yishingiz mumkin emas. Sizning vazifangiz buni bajarish uchun minimal qancha amal ketishini topishdan iborat.

$n = 4$ holat uchun optimal yo'lni havola etamiz.

Kiruvchi ma’lumotlar:

Birinchi qatorda natural son $n(1 \le n \le 10^{36})$.

Chiquvchi ma’lumotlar:

Yagona qatorda masala yechimini chiqaring. Javob katta bo'lib ketishi mumkin, shuning uchun uni $10^9 + 7$ ga bo'lgandaki qoldiqini chiqaring.