D. Шинэ жил ба эртний мэргэ

хугацааны хязгаарлалт 2.5 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Лимак бол бяцхан туйлын баавгай юм.Тэрээр цаснаас нэгэн эртний мэргэтэй хуйлаас олжээ.Лимак ямар ч эртний хэл мэдэхгүй ба иймд мэргийг ойлгох боломжгүй байгаа юм.Гэхдээ тэр цифрүүдийг мэднэ!

Мэргийн нэг хэсэг нь $n$ ширхэг цифр бүхий дараалал байх юм.Эхний цифр нь 0 биш ба Лимак энэ нь ямар нэг онцгой жилүүдийн бүртгэл хэмээн бодож байгаа аж.Ямар ч таслал болон зайнууд нь олж харахад маш бэрх ба магадгүй эртний хүмүүс эдгээрийг ашигладаггүй байсан.Одоо Лимак ямар жилүүд тэнд бүртгэгдсэн байгааг гайхаж байв.

Лимак 3-н зүйлийн таамаглаж байв:

  • Жилүүд нь заавал өсөх дарааллаар бүртгэгдсэн;
  • Жил болгон нь эерэг бүхэл тоо байна;
  • Ямар ч жил нь 0-ээр эхлээгүй байна.

Лимак дээрх нөхцөлүүдийг хангаж байхаар дарааллыг тоонуудад (жилүүдэд) хуваах бүх боломжит аргуудыг авч үзэх юм.Тэрээр үүнийг ямар нэг тусламжгүйгээр хийнэ.Гэсэн хэдий ч тэрээр танаас ингэж хийх нийт хэчнээн арга байгааг хэлж өгөхийг хүсжээ.Уг тоо нь магадгүй маш том тоо байж болох учраас,та уг тоог $10^{9} + 7$ модулаар бодож өгнө үү.

Оролт

Эхний мөрөнд цифрүүдийн тоо болох ганц бүхэл тоо $n$ ($1 ≤ n ≤ 5000$) өгөгдөнө.

2-дахь мөрөнд $n$ урттай цифрүүдийн тэмдэгт мөр өгөгдөнө.Эхний цифр нь '$0$'-ээс ялгаатай байна.

Гаралт

Өгөгдсөн дарааллыг зөвөөр хуваах боломжийн тоог $10^{9} + 7$ модулаар бодож хэвлэнэ.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
6
123434
Гаралт
8
Оролт
8
20152016
Гаралт
4

Тэмдэглэл

Эхний жишээнд дарааллыг хуваах $8$ арга байна:

  • "$123434$" = "$123434$" (өгөгдсөн дараалал нь магадгүй ганц том тоо байж болно.)
  • "$123434$" = "$1$" + "$23434$"
  • "$123434$" = "$12$" + "$3434$"
  • "$123434$" = "$123$" + "$434$"
  • "$123434$" = "$1$" + "$23$" + "$434$"
  • "$123434$" = "$1$" + "$2$" + "$3434$"
  • "$123434$" = "$1$" + "$2$" + "$3$" + "$434$"
  • "$123434$" = "$1$" + "$2$" + "$3$" + "$4$" + "$34$"

Бид "123434$" = "12$" + "34$" + "34$" гэсэн хуваалтыг тооцохгүй байгааг анхаарна уу.Учир нь тоонууд нь заавал өсөж байх юм.

2-дахь жишээнд $4$ арга байна:

  • "$20152016$" = "$20152016$"
  • "$20152016$" = "$20$" + "$152016$"
  • "$20152016$" = "$201$" + "$52016$"
  • "$20152016$" = "$2015$" + "$2016$"
Сэтгэгдлүүдийг ачааллаж байна...