Background

石老板 每次在水群的时候说 ”加训！加训！加训！“，群里就会有一群支持他的粉丝。每个粉丝都会举一个牌子，每个牌子上面只会有 1,2...9，以及 ?，如果牌子上面是数字表示已经确定，否则是不确定的，现在 石老板 想多了解一下他的粉丝，他会根据总喜欢度对其进行判定他的粉丝到底有多喜欢他。

Description

总喜欢度是所有可能组成的数字的喜欢度之和。

而对于****喜欢度的定义：

**不改变牌子的任何顺序，让所有的 **? 变成确定的值组成一串数字，让这串数字减去确定的所有牌子上的数字总和（不算曾经是 ? 的那些数字），但是群友都非常喜欢玩原神，他们经常性的在群里大喊 “原神，启动！” 来吸引了大量的粉丝，现在导致支持 石老板 的粉丝就只剩下这串数字模九的结果了，模九后的数字，就是一次喜欢度。

例如：2?03 的一种可能的数字是 2203，2203-(2+0+3)=2198，那么此时的喜欢度是 2198%9=2。

13?? 可能组成的部分数字是 1311,1376,1349,1314。

由于每个 ? 都有九种可能的数字，所以如果 ? 很多的话组成的数字所构成的喜欢度的个数也会特别多，石老板 为此十分头疼，你作为 石老板 的忠实粉丝~~（你不喜欢玩原神，对吧）~~，所以你不会被这三个 "原神学长" 说 "原神，启动！“ 而被干扰，你会帮助 石老板 解决这个麻烦，由于总喜欢度特别大，请输出对 5201314 取模的答案。

Format

Input

第一行输入一个整数 n($1\leq n \leq 10^6$)，表示牌子的总个数。

**第二行输入一个长度为 n 的字符串 s，每个字符表示一个牌子，牌子上只会标出 $1,2\dots 9$ 或者 **?。

Output

输出一行，包含一个整数表示总喜欢度。

Samples

3
1?1

36

13
?1?1?4?5?1?4?

3527934

Limitation

第一个样例可能的数字有 111,121,131,141,151,161,171,181,191，分别减掉已有的数字然后取模九得到的喜欢度是 1,2,3,4,5,6,7,8,0，因此，总喜欢度为 36。

1s, 1024KiB for each test case.