נתונה מחרוזת המורכבת מ-$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