题目内容

小蓝正在分析一段由数字组成的密码，他想统计密码中有多少个子序列满足以下模式：先出现两个连续的数字 1，接着出现一个数字 4，最后出现一个数字 5。换句话说，需要按下标顺序选取四个位置 $i_1 \lt i_2 \lt i_3 \lt i_4$，要求 $i_2 = i_1 + 1$，并且这四个位置上的字符依次为 1、1、4、5。这样的子序列称为“特殊序列”。请计算密码中特殊序列的数量。由于答案可能很大，请将结果对 $10^9+7$ 取模后输出。

密码长度 $n$ 满足 $1 \le n \le 10^6$，字符串 $s$ 仅由数字字符组成。

输入描述

第一行输入一个整数 $n$，表示字符串的长度。 第二行输入一个长度为 $n$ 的字符串 $s$，仅包含数字字符。