کلاس‌هاکالجبانک سؤالاتمسابقاتکاریابیجونیورابوت‌کمپ
کلاس‌ها کالج بانک سؤالات مسابقات کاریابی جونیورا بوت‌کمپ
ورود
ورود به بخش شرکت‌هاورودعضویت
  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

روی تخته عدد nn نوشته شده است. کاپیتان می‌خواهد با انجام تعدادی عملیات این عدد را به ۱ تبدیل کند. او در هر عملیات می‌تواند عدد نوشته شده روی تخته را با یکی از مقسوم‌علیه‌های طبیعی کوچک‌تر از آن عدد جایگزین کند.

از آن‌جایی که او می‌خواهد حداکثر استفاده را از تخته گچی بکند، باید طوری این کار را انجام دهد که تعداد عملیات‌ها حداکثر باشد.

به چند طریق می‌تواند این عملیات‌ها را انجام دهد به طوری که حداکثر تعداد مرحله را طی کند. دو روش را متقاوت در نظر بگیرید، اگر دنباله‌ی اعدادی که روی تخته نوشته می‌شود متفاوت باشد.

ورودی

در تنها سطر ورودی، عدد صحیح و مثبت nn داده می‌شود. 1≤n≤10181 \leq n \leq 10^{18}

خروجی

باقی‌مانده‌ی پاسخ مسئله بر 109+710^9 + 7 را چاپ کنید.

مثال‌ها

ورودی نمونه ۱

7
Plain text

خروجی نمونه ۱

1
Plain text

توضیح نمونه ۱

تنها روش ممکن 7→1 7 \to 1

است. بنابراین پاسخ ۱ می‌شود.

ورودی نمونه ۲

15
Plain text

خروجی نمونه ۲

2
Plain text

توضیح نمونه ۲

حداکثر طول ممکن ۳ است و ۲ روش 15→5→115 \to 5 \to 1 15→3→115 \to 3 \to 1 وجود دارد. بنابراین پاسخ برابر ۲ است.

ورودی نمونه ۳

12
Plain text

خروجی نمونه ۳

3
Plain text

توضیح نمونه ۳

حداکثر طول ممکن ۴ است و ۳ روش 12→6→3→112 \to 6 \to 3 \to 1 12→6→2→112 \to 6 \to 2 \to 1 12→4→2→112 \to 4 \to 2 \to 1 وجود دارد. بنابراین پاسخ برابر ۳ است.

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.