Бізде нөлге тең емес $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$) берілген.

Екінші жолда 1–9 цифрларынан тұратын ұзындығы $n$ жол берілген.

Шығыс деректер

Барлық өрнектердің қосындысын $10^9 + 7$ модулі бойынша білдіретін бір бүтін санды шығарыңыз.

Мысал

Кіріс

3
231

Шығыс

397