题解

题面描述

给定一个仅由字符 $0,1,2,\ldots,9$ 组成的长度为 $n$ 的字符串 $t$。定义一个数字字符串的权值为其所有子串中同时满足以下两个条件的子串数量：

1. 子串所表示的整数为偶数，即末尾数字属于集合 $\{0,2,4,6,8\}$；
2. 子串不存在前导零（例如 “$02$” 或 “$020$” 均不合法），但单个字符 “$0$” 是合法的。

现在要求，对于给定的字符串 $t$，求其所有子串的权值之和。由于答案可能很大，输出结果需要对 $10^9+7$ 取模。

题目内容

小红定义，一个由$0,1,2,...,9$这十个数字构成的数字字符串的权值为，它的全部子串中，同时

满足下方这两个条件的数量:

$1.$字符串所表示的整数是偶数，即末尾数字属{$0,2,4,6,8$};

$2.$字符串不存在前导零(例如"$02$"或"$020$"均不合法)，但单个字符$0$ 是合法的。

小红现在想知道，对于给定的数字字符串$t$，它的全部子串的权值之和是多少。由于答案可能很大，请将答案对$(10^9+7)$取模后输出。

子串为从原字符串中，连续的选择一段字符(可以全选、可以不选)得到的新字符串。

输入描述

第一行:一个正整数$n(1 ≤n≤2×10^5)$代表字符串$t$的长度。

第二行:一个长度为$n$，仅由字符$0$到$9$组成的字符串$t$。

输出描述

一个整数，表示小红的数字字符串中所有子串的权值之和，结果对$10^9+7$取模。

样例1

输入

3
203

输出

9

说明

字符串“$203$"有六个子串:

• "$2$"，权值为$1$;
• "$0$"，权值为$1$;
• "$3$"，权值为$0$;
• "$20$"，权值为$3$;
• "$03$"，权值为$1$;
• "$203$"，权值为$3$; 综上，答案为 $9$

样例2

输入

3
202

输出

13