You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

一个个瞬间，积累起来就是一辈子。 —— Tomori

Tomori看向Anon，真诚地问道：“你能和我一组一辈子乐队吗？”但Anon没有回答她。回到家后，Tomori仍想知道她能和Anon组多久乐队，于是她找到了一个由数字0到9组成的字符串，并计算了其中所有合法日期的子序列的数量，并且她认为这就是她能和Anon一起组成乐队的天数。然而，计算子序列并不是一件简单的事情，所以Tomori找到你，请你帮她计算这个答案。

Description

具体地，你将得到一个只由数字0到9组成的字符串S，你需要计算其中所有合法日期的子序列的数量。由于这个答案可能很大，请你输出答案模998244353的值。

S的一个子序列是从S中删除零个或多个元素，剩下元素保持原本的顺序得到的序列。 合法日期T的定义如下：

• |T| = 8。

• T的前四个数字表示年份Y ，接下来的两个数字表示月份M，再接下来的两个数字表示日期D。例 如，合法日期T，当Y = 2025, M = 4, D = 20时为20250420，而当Y = 1, M = 1, D = 1时，合法日期T为00010101。

• 年份Y 应满足1 ≤ Y ≤ 9999，对于M和D没有进一步的限制，除了日期必须是现实中存在的。 在这个问题中，我们使用常见的闰年规则。一个年份被称为闰年当且仅当：

该年份能被4整除；并且该年份不能被100整除，除非它也能被400整除。

否则，该年份称为平年。例如，2000是一个闰年，但1900是一个平年。每个月的天数如下表所示。

Format

Input

输入第一行包含一个整数n(1 ≤ n ≤ $10^5$ ) — 字符串S的长度。

第二行包含一个长度为n的字符串S，仅由数字0到9组成。

Output

输出一个整数，即Tomori能与Anon组多少天乐队，模998244353。

Samples

测试用例

8
20250420

1

8
00000101

0

8
00010101

1

10
0123401234

10

Limitation

1s, 1024KiB for each test case.