شناسه سوال

  • تعداد حل: 2 حل
  • محدودیت حافظه: 256 مگابایت
  • محدودیت زمان: 10 ثانیه
  • دسته‌بندی: الگوریتمی
  • زمان ایجاد: 1401/04/04

رشته افسانه‌ای


ما در کتابی، دستور ساخت یک رشته افسانه‌ای رو پیدا کردیم! برای ساخت این رشته، باید n را داشته باشه و رشته sn رو به روش زیر درست کنیم! :

اگر n=1 :

sn  = "1"

اگر n>1 :

sn = sn -1 + "n" + sn-1

در این سوال منظورمون از جمع دو رشته مثلا a و b یعنی رشته ای که از چسبوندن رشته a در سمت چپ b به دست میاد. و همینطور منظور از "n" یعنی نمایش عدد n به صورت رشته.

بنابراین:

s1 = "1"

s2 = "121"

s3 = "1213121"

...

خب دستور ساخت رشته تموم شد بریم سراغ خود سوال!

ما در ورودی این سوال، عدد صحیح n رو میدیم و شما باید در خروجی، مجموع اعداد رشته sn رو برگردونید. چون ممکنه این عدد خیلی بزرگ باشه، باقی مونده عدد حاصل رو بر 109 + 7 محاسبه کنید.

 


مثال)

Input:
1
- - - - - - - - - -
Output:
1

رشته s1 برابر با "1" هست که مجموعش میشه 1

 

مثال)

Input:
2
- - - - - - - - - -
Output:
4

رشته s2 برابر با "121" هست که مجموع ارقامش میشه 1+2+1=4

 

مثال)

Input:
3
- - - - - - - - - -
Output:
11

1+2+1+3+1+2+1=11