+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روی تخته عدد $n$ نوشته شده است. کاپیتان می‌خواهد با انجام تعدادی عملیات این عدد را به ۱ تبدیل کند. او در هر عملیات می‌تواند عدد نوشته شده روی تخته را با یکی از مقسوم‌علیه‌های طبیعی کوچک‌تر از آن عدد جایگزین کند. از آن‌جایی که او می‌خواهد حداکثر استفاده را از تخته گچی بکند، باید طوری این کار را انجام دهد که تعداد عملیات‌ها حداکثر باشد. به چند طریق می‌تواند این عملیات‌ها را انجام دهد به طوری که حداکثر تعداد مرحله را طی کند. دو روش را متقاوت در نظر بگیرید، اگر دنباله‌ی اعدادی که روی تخته نوشته می‌شود متفاوت باشد. # ورودی در تنها سطر ورودی، عدد صحیح و مثبت $n$ داده می‌شود. $$1 \leq n \leq 10^{18}$$ # خروجی باقی‌مانده‌ی پاسخ مسئله بر $10^9 + 7$ را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 7 ```` ## خروجی نمونه ۱ ``` 1 ```` <details> <summary> **توضیح نمونه ۱** </summary> ---------- تنها روش ممکن $$ 7 \to 1 $$ است. بنابراین پاسخ ۱ می‌شود. ---------- </details> ## ورودی نمونه ۲ ``` 15 ```` ## خروجی نمونه ۲ ``` 2 ```` <details> <summary> **توضیح نمونه ۲** </summary> ---------- حداکثر طول ممکن ۳ است و ۲ روش $$15 \to 5 \to 1$$ $$15 \to 3 \to 1$$ وجود دارد. بنابراین پاسخ برابر ۲ است. ---------- </details> ## ورودی نمونه ۳ ``` 12 ```` ## خروجی نمونه ۳ ``` 3 ```` <details> <summary> **توضیح نمونه ۳** </summary> ---------- حداکثر طول ممکن ۴ است و ۳ روش $$12 \to 6 \to 3 \to 1$$ $$12 \to 6 \to 2 \to 1$$ $$12 \to 4 \to 2 \to 1$$ وجود دارد. بنابراین پاسخ برابر ۳ است. ---------- </details>

حل سؤال در بانک سؤالات