被3整除

描述

给定一个位数不大于50的数字，判断有多少子序列能够被3整除？答案可能比较大，需要对1e9+7取模

输入描述

一个数（位数不超过50）

输出描述

能够被3整除的子序列个数

用例输入 1 

132

用例输出 1 

3

用例输入 2 

333

用例输出 2 

7

用例输入 3 

123456

用例输出 3 

23

提示

132可以有 12 3和132三个子序列被3整除，21不是，因为不是子序列