该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

游游的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的倍数。