جک بعد از اینکه به دوستان المپیاد کامپیوتری خود خیانت کرد و به سمت المپیاد ریاضی رفت، در کلاس های المپیاد ریاضی ثبت نام کرد. در هفته اول ۳ کلاس جبر، ترکیبیات و نظریه اعداد داشت. در کلاس جبر با تابع و در کلاس نظریه اعداد با ب.م.م (بزرگترین مقسوم علیه مشترک) و در کلاس ترکیبیات با مفاهیم جایگشت آشنا شد.

حال او آموخته های خود را ترکیب کرده و تابع $f(x)$ را به شکل زیر ساخته است:

$f(x)$ برابر بزرگترین مقسوم علیه مشترک تمامی عددهایی است که ممکن است از جایگشت دادن ارقام عدد $x$ به دست بیاید؛ برای مثال برای عدد ۱۲۰، جایگشت‌های ممکن برابر $\langle 12, 21, 102, 120, 201, 210 \rangle$ است که ب.م.م آن‌ها برابر ۳ است.

حال سوالی که برای جک پیش آمده این است که اگر به ازای همه‌ی اعداد ۱ تا $n$ مقدار $f(x)$ را حساب و جمع کنیم به چه عددی می‌رسیم؟

او این سوال را پیش دوستان المپیاد ریاضی خود مطرح کرد ولی دوستان او در حل این مسئله ناتوان بودند. او دست از پا درازتر پیش دوستان المپیاد کامپیوتری خود آمد و سوالش را به آن‌ها گفت تا برایش حل کنند.

دوستان او از اینکه جک به آن‌ها خیانت کرده بود، ناراحت بودند و به دنبال انتقام بودند؛ از این رو سوال او را دزدیدند و برای فاینال‌های عملی پیشنهاد دادند. از آنجا که سوال جک مورد قبول واقع شد، شما باید این سوال را حل کنید!

در تنها خط ورودی عدد $n$ داده می‌شود.

در تنها خط خروجی جواب سوال جک یا همان $\displaystyle \sum_{i=1}^{n} f(i)$ را چاپ کنید.

• $1 \leq n < 10^{5,001}$
• عدد ورودی صفر پشت عدد ندارد.

• زیرمسئله اول (۸ نمره): $n \leq 10^6$.
• زیرمسئله دوم (۳۵ نمره): $n \leq 10^{18}$.
• زیرمسئله سوم (۲۹ نمره): $n < 10^{501}$.
• زیرمسئله چهارم (۲۸ نمره): بدون محدودیت اضافی.