1-6 游游的9的倍数

1-6 游游的9的倍数

游游的9的倍数

链接:https://ac.nowcoder.com/acm/contest/60245/D
来源:牛客网

时间限制:C/C++ 1秒
空间限制:C/C++ 262144K

题目描述

游游拿到了一个数字串,她想取一个该数字串的子序列(子序列在原串中可以不连续),使得该子序列是9的倍数。子序列可以包含前导零。
游游想知道,一共能取多少个合法的子序列?答案请对 \(10^9+7\) 取模。
我们定义,若两个子序列在原串中的位置不同,则认为它们不同。

输入描述:

一个长度不超过200000的,仅由'0'~'9' 十种字符组成的字符串。

输出描述:

子序列是9的倍数的数量。答案请对 \(10^9+7\) 取模。

示例1

输入

1188

输出

5

说明

共可以取4个不同的"18"子序列,和一个"1188"子序列,都是9的倍数。

示例2

输入

0123

输出

1

说明

只有子序列"0"是9的倍数。

信息

ID
1422
难度
7
分类
(无)
标签
(无)
递交数
53
已通过
11
通过率
21%
上传者

相关