เรามีสตริงที่ประกอบด้วยตัวเลขที่ไม่ใช่ศูนย์จำนวน $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