26494번 - Date 서브태스크다국어

Fujiwara-san loves dates! She calls a date a string of form $y/m/d$ where $d$, $m$ and $y$ are positive integers without leading zeroes that represent a calendar date ($d$ is the day, $m$ is the month, $y$ is the year). The precise rules for a valid date is the following:

• $y ∈ \{1, 2, \dots\}$.
• $m ∈ \{1, \dots , 12\}$.
• If $m ∈ \{1, 3, 5, 7, 8, 10, 12\}$, then $d ∈ \{1, \dots , 31\}$.
• If $m ∈ \{4, 6, 9, 11\}$, then $d ∈ \{1, \dots , 30\}$.
• If $m = 2$ and $y$ is either a not a multiple of $4$, or both a multiple of $100$ and not a multiple of $400$, then $d ∈ \{1, \dots , 28\}$.
• If $m = 2$ and $y$ is a multiple of $4$, and either not a multiple of $100$ or a multiple of $400$, then $d ∈ \{1, \dots , 29\}$.

For example, $2022/2/14$, $2024/2/29$ and $2000/2/29$ are valid dates; whereas $2022/02/14$, $2022/2/29$ and $2100/2/29$ are not valid dates.

Fujiwara-san has recently received a sequence of symbols $s_1, \dots , s_n$, where $s_i ∈ \{0, 1, \dots , 9, /\}$. She now wants to ask: how many sequences of indices $1 ≤ i_1 < \dots < i_k ≤ n$ exist such that $s_{i_1} , \dots , s_{i_k}$ are a valid date?

The first line of the input contains the integer $n$. The second line contains the symbols $s_1, \dots , s_n$, not separated by spaces.

Output the answer modulo $10^9 + 7$.

• $1 ≤ n ≤ 100\,000$.