题目描述

藤原小姐非常喜欢日期！她称一个形如 y/m/d 的字符串为一个日期，其中 $d,m,y$ 均为不含前导零的正整数，分别表示日、月、年。

一个日期合法，当且仅当满足以下规则：

• $y\ge 1$；
• $1\le m\le 12$；
• 若 $m\in\{1,3,5,7,8,10,12\}$，则 $1\le d\le 31$；
• 若 $m\in\{4,6,9,11\}$，则 $1\le d\le 30$；
• 若 $m=2$ 且年份不是闰年，则 $1\le d\le 28$；
• 若 $m=2$ 且年份是闰年，则 $1\le d\le 29$。

年份 $y$ 是闰年，当且仅当：

• $y$ 是 $4$ 的倍数；并且
• $y$ 不是 $100$ 的倍数，或者 $y$ 是 $400$ 的倍数。

例如，2022/2/14、2024/2/29 和 2000/2/29 是合法日期；而 2022/02/14、2022/2/29 和 2100/2/29 不是合法日期。

现在给定一个由数字字符 0 到 9 以及字符 / 组成的字符串

请计算有多少个严格递增的下标序列

使得由字符

组成的字符串是一个合法日期。

换言之，需要统计原字符串中有多少个子序列能够组成合法日期。

输入格式

第一行包含一个整数 $n$。

第二行包含一个长度为 $n$ 的字符串，字符之间没有空格，且每个字符均为数字或 /。

输出格式

输出合法日期子序列的数量，对 $10^9+7$ 取模。

数据范围

子任务

样例 1

输入：
8
55/55/55

输出：
12

样例说明

5/5/5 在原字符串中出现了 $8$ 次，55/5/5 出现了 $4$ 次。

样例 2

输入：
7
44/2/29

输出：
9

样例说明

4/2/2、4/2/9、4/2/29 各出现 $2$ 次；44/2/2、44/2/9、44/2/29 各出现 $1$ 次。

样例 3

输入：
8
11/11/31

输出：
24

样例说明

1/1/1、1/1/3、1/1/31 各出现 $4$ 次；1/11/1、1/11/3、11/1/1、11/1/3、11/1/31 各出现 $2$ 次；11/11/1、11/11/3 各出现 $1$ 次。

样例 4

输入：
22
11/2/43432/534/123/234

输出：
66078