题目描述

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

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

具体地，你将得到一个只由数字 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$ 是一个平年。每个月的天数如下表所示。

输入格式

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

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

输出格式

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

8
20250420

1

8
00000101

0

8
00010101

1

10
0123401234

10