7384: 被3整除的子序列
[Creator : ]
Description
给你一个长度为 $5 \times 10^6$ 的数字串，问你有多少个子序列构成的数字可以被 3 整除。
答案对 $10^9+7$ 取模。
答案对 $10^9+7$ 取模。
Input
输入一个字符串，由数字构成。
Output
输出一个整数。
Sample 1 Input
132
Sample 1 Output
3
Sample 2 Input
9
Sample 2 Output
1
Sample 3 Input
333
Sample 3 Output
7
123456
23
Sample 4 Input
00
Sample 4 Output
3