#P16249. [infO(1) Cup2022]date

[infO(1) Cup2022]date

题目描述

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

一个日期合法,当且仅当满足以下规则:

  • y≥1y\ge 1;
  • 1≤m≤121\le m\le 12;
  • 若 m∈{1,3,5,7,8,10,12}m\in\{1,3,5,7,8,10,12\},则 1≤d≤311\le d\le 31;
  • 若 m∈{4,6,9,11}m\in\{4,6,9,11\},则 1≤d≤301\le d\le 30;
  • 若 m=2m=2 且年份不是闰年,则 1≤d≤281\le d\le 28;
  • 若 m=2m=2 且年份是闰年,则 1≤d≤291\le d\le 29。

年份 yy 是闰年,当且仅当:

  • yy 是 44 的倍数;并且
  • yy 不是 100100 的倍数,或者 yy 是 400400 的倍数。

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

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

s1s2⋯sn.s_1s_2\cdots s_n.

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

1≤i1<i2<⋯<ik≤n,1\le i_1<i_2<\cdots<i_k\le n,

使得由字符

si1si2⋯siks_{i_1}s_{i_2}\cdots s_{i_k}

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

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

输入格式

第一行包含一个整数 nn。

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

输出格式

输出合法日期子序列的数量,对 109+710^9+7 取模。

数据范围

1≤n≤100000.1\le n\le 100000.

子任务

子任务 分值 限制
1 12 n≤15n\le 15
2 7 n≤1000n\le 1000,且 si∈{5,/}s_i\in\{5,/\}
3 8 si∈{5,/}s_i\in\{5,/\}
4 7 si=/s_i=/ 或 si≥5s_i\ge 5
5 8 si≠0s_i\ne 0 且 si≠2s_i\ne 2
6 9 n≤1000n\le 1000,且 si≠2s_i\ne 2
7 11 si≠2s_i\ne 2
8 38 无额外限制

样例 1

输入:
8
55/55/55

输出:
12

样例说明

5/5/5 在原字符串中出现了 88 次,55/5/5 出现了 44 次。

样例 2

输入:
7
44/2/29

输出:
9

样例说明

4/2/2、4/2/9、4/2/29 各出现 22 次;44/2/2、44/2/9、44/2/29 各出现 11 次。

样例 3

输入:
8
11/11/31

输出:
24

样例说明

1/1/1、1/1/3、1/1/31 各出现 44 次;1/11/1、1/11/3、11/1/1、11/1/3、11/1/31 各出现 22 次;11/11/1、11/11/3 各出现 11 次。

样例 4

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

输出:
66078