E. Энд тэндгүй нэмэх тэмдэг

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

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

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

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

Вася маш уйтгартай математикийн хичээл дээр сууж байна. Хөгжилтэй байхын тулд тэр цаасан дээр $n$ ширхэг тоонуудыг нэг мөрөнд бичжээ. Үүний дараа үр дүнд нь зөв арифметик илэрхийлэл үүссэн байхаар мөрөнд байгаа зарим цифрүүдийн хооронд янз бүрийн аргаар нэмэх тэмдэг ("$+$") бичиж эхлэв. Томъёолбол хоёр нэмэх тэмдгийг зэрэгцээ бичиж болохгүй, өөрөөр хэлбэл зэргэлдээ хоёр нэмэх тэмдгийн дунд ядаж нэг цифр байна. Мөн мөрийн эхлэлд эсвэл төгсгөлд нэмэх тэмдэг тавьж болохгүй. Жишээлбэл, $100500$ тэмдэгт мөрөнд $100500$ (нэмэх тэмдэггүй), $1+00+500$, $10050+0$ байвал зөв, харин $100++500$, $+1+0+0+5+0+0$, $100500+$ байвал буруу тавьсан гэсэн үг.

Хичээл их удаан үргэлжилж байсан ба Вася $k$ ширхэг нэмэх тэмдгийг зөв байрлуулах бүх аргыг бичжээ. Яг энэ үед тэр багшдаа баригдаад хичээлийн төгсгөлд өөрийн бичсэн бүх арифметик илэрхийллийнхээ нийлбэрийг олох даалгавар авчээ. Хариулт хэтэрхий том байж болох тул $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ. Васяд туслаарай!

Оролт

Эхний мөрөнд $n$ болон $k$ ($0 ≤ k < n ≤ 10^{5}$) бүхэл тоонууд байна.

Хоёр дахь мөрөнд $n$ цифрүүдээс бүрдсэн тэмдэгт мөр байна.

Гаралт

Хариуг $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
3 1
108
Гаралт
27
Оролт
3 2
108
Гаралт
9

Тэмдэглэл

Эхний жишээний хариу: $(1 + 08) + (10 + 8) = 27$.

Хоёр дахь жишээний хариу: $1 + 0 + 8 = 9$.

Сэтгэгдлүүдийг ачааллаж байна...