游游的9的倍数
题号：NC254017
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

子序列是9的倍数的数量。答案请对  取模。
示例1

输入

复制 
1188

输出

复制 
5

说明

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

输入

复制 
0123

输出

复制 
1

说明

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