Description

Hrahc is a 24-year-old student. He likes a number $\texttt{114514}$ very much.

Now Hrahc gets a string with numbers. He wants to know how many times the number $\texttt{114514}$ appears as a subsequence (not substring, notice that subsequence is not required to be contiguous) in the string.

Format

Input

The first line contains a single integer $n\,(1\leq n\leq 10^6)$, the length of the string.

The second line contains a string of length $n$, consisting of digits from $\texttt{0}$ to $\texttt{9}$.

Output

Only one integer: the number of times the number $\texttt{114514}$ appears as a subsequence in the string.

Modulo 114514.

Samples

6
114514

1

7
1114514

3