解题思路

问题分析

我们需要统计字符串 t 的所有非空子序列，满足以下两点才算有效：

1. 无前导零：除单个字符 "0" 以外，不允许以 '0' 开头。
2. 数字和可被 5 整除。

对每个有效子序列，根据其首位和末位数字分别给分：

• 若首位是质数 {2,3,5,7} 且末位是偶数 → 4 分

题目内容

现给定一个仅由数字 $0,1,2,...,9$构成的字符串$t$，系统将基于t的所有非空子序列计算奖励分数。

一个子序列被认为是有效的必须同时满足以下条件：

1、子序列所表示的整数不得包含前导零(例如$01$、$007$均不合法)，但单个字符0被视为合 法: 2.子序列中所有数字之和须能被$5$整除，即$\sum_{digit∈子序列}\ digit=0(mod\ 0)$

对于每个有效子序列，系统根据以下规则给予奖励:

1. 若有效子序列的首位数字属于{$2, 3, 5,7$}(即素数数字)且末位数字为偶数，则奖励分数为$4$分;
2. 若有效子序列的首位数字属干{$2,3,5,7$}
3. 其余有效子序列奖励$1$分。

请计算字符串$t$的所有非空有效子序列的累计奖励分数，并输出结果对$(10^9+7)$取模后的值。

【名词解释】

• 子序列:子序列为从原字符串中删除任意个(可以为零或全部)字符得到的新字符串，字符的 相对顺序保持不变。
• 前导零:前导零指数字字符串最前面的多余零，例如"$01$"中的$0$被视为前导零；但单独的"$0$" 被视为合法。
• 素数数字: 指$2、3、5、7$四个数字，它们均为质数。

注意，子序列在选取时必须保持原字符串中字符的顺序不变。

输入描述

输入一个仅由数字$0,1,2,...,9$组成的字符串$t$，其中字符串长度满足$(1≦|t|≤10^5)$

输出描述

输出一个整数，表示字符串$t$的所有非空有效子序列的累计奖励分数对$(10^9+7)$取模后的结果。

样例1

输入

248

输出

4

说明

对于这组样例:

• 字符串“$248$"的所有非空子序列为:

  • "$2$": 数字和为$2$，不满足$2≠0 (mod\ 5)$;

  • "$4$": 数字和为$4$;

  • "$8$": 数字和为$8$;

  • "$24$": 数字和为$2+4=6$;

  • "$28$": 数字和为$2+8=10$，满足条件;

  • "$48$": 数字和为$4+8=12$;

  • "$248$": 数字和为$2+4+8=14$;

其中，只有“$28$”为有效子序列，其首位数字为$2$(属于{$2,3,5,7$})，末位数字为$8$(偶数)，因此奖励$4$分。

样例2

输入

205

输出

4

说明

对于这组样例:

• 字符串“$205$”的非空子序列包括:

  • "$0$": 合法(单个零)，数字和为$0$满足条件，奖励 $1$分;

  • "$5$": 数字和为$5$，其首位为’$5$’(属于 {$2,3,5,7$})，末位为’$5$’(奇数)，奖励$3$分;其他子序列因前导零或数字和不满足条件而无效。

累计奖励分数为$1+3=4$分。