6678: 被 3 整除的子序列
[Creator : ]
Description
给你一个长度为 $50$ 的数字串，问你有多少个子序列构成的数字可以被 $3$ 整除。答案对 $10^9+7$ 取模。
Input
输入一个字符串，由数字构成，长度小于等于 $50$。
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