All lucky substrings

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Zenyk has a lucky string \(s\) of length \(n\). One day Marichka asked him what the sum of all its substrings is. Zenyk finds it difficult to answer this question, so he asks for your help.

Since the answer can be very large, output it modulo the prime number \(998244353\).

Input

The first line contains a single integer \(n\) — the length of Zenyk’s string.

The second line contains the string \(s\) itself.

Output

Output the sum of all substrings modulo \(998244353\).

Constraints

\(1 \le n \le 10^6\),

\(s\) consists only of the characters 4 and 7.

Samples

Input (stdin) сopy	Output (stdout) сopy
2 47	58

Input (stdin) сopy	Output (stdout) сopy
4 4774	6245

Notes

In the first example, the sum of all substrings is: \(4 + 7 + 47 = 58\).

In the second example, the sum of all substrings is: \(4 + 7 + 7 + 4 + 47 + 77 + 74 + 477 + 774 + 4774 = 6245\).