لدينا سلسلة نصية تتكون من $n$ أرقام غير صفرية. يمكننا تكوين تعبير رياضي عن طريق إدراج رمز واحد على الأكثر من الرمزين $+$ (جمع) أو $\cdot$ (ضرب) بين أي رقمين متتاليين. على سبيل المثال، من السلسلة 231 يمكننا تكوين تسعة تعابير:

$231$, $23 + 1$, $23 \cdot 1$, $2 + 31$, $2 \cdot 31$, $2 + 3 + 1$, $2 + 3 \cdot 1$, $2 \cdot 3 + 1$, $2 \cdot 3 \cdot 1$.

نقوم بحساب قيم هذه التعابير وفقاً للترتيب القياسي للعمليات الحسابية، ثم نحسب مجموع كل القيم. في مثالنا نحصل على

$$231 + 24 + 23 + 33 + 62 + 6 + 5 + 7 + 6 = 397$$

احسب المجموع أعلاه بباقي القسمة على $10^9 + 7$.

الإدخال

يحتوي السطر الأول من الإدخال على عدد صحيح واحد $n$ ($1 \le n \le 10^6$)، يمثل طول السلسلة.

يحتوي السطر الثاني على سلسلة طولها $n$ تتكون من الأرقام 1–9.

الإخراج

اطبع عدداً صحيحاً واحداً، وهو مجموع جميع التعابير بباقي القسمة على $10^9 + 7$.

مثال

الإدخال

3
231

الإخراج

397