#P1886. 2024.08.14-OPPO-第3题-1145子串

2024.08.14-OPPO-第3题-1145子串

题目描述

小O有一个长度为 nn 的数字字符串 ss，他想知道 ss 中含有多少个 "1145" 子串序列。

"1145" 子串序列是指由两个连续的数字 "1"、一个数字 "4" 和一个数字 "5" 组成的字符串，在这里，我们依据数字在原字符串中的下标大小决定顺序。

输入描述

第一行输入一个整数 nn (1≤n≤1061 \leq n \leq 10^6) 代表字符串的长度。

第二行输入一个长度为 nn，且仅包含数字字符的字符串 ss。

输出描述

在一行上输出一个整数，表示数字字符串 ss 中 "1145" 子串序列的个数。由于结果可能很大，因此输出结果对 109+710^9 + 7 取模的结果。

示例 1

输入

5
11145

输出

2

说明

两种子串序列分别为：s1s2s4s5s_1s_2s_4s_5 和 s2s3s4s5s_2s_3s_4s_5。注意，"11" 必须是连续的。

示例 2

输入

5
01154

输出

0

知识点:*****

查看知识点以及同类型题目

Statistics