被3整除的子序列
题号：NC21302
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给你一个长度为50的数字串,问你有多少个子序列构成的数字可以被3整除
答案对1e9+7取模

输入描述:

输入一个字符串，由数字构成，长度小于等于50

输出描述:

输出一个整数
示例1

输入

复制 
132

输出

复制 
3
示例2

输入

复制 
9

输出

复制 
1
示例3

输入

复制 
333

输出

复制 
7
示例4

输入

复制 
123456

输出

复制 
23
示例5

输入

复制 
00

输出

复制 
3

备注:

n为长度
子任务1: n <= 5
子任务2: n <= 20
子任务3: 无限制