数位DP
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个正整数 n，你可以对 n 进行任意次（包括零次）如下操作：
  • 选择 n 上的某一数位，将其删去，剩下的左右部分合并。例如 123，你可以选择删去第二位 2，得到新数 13。
在对 n 进行操作后，请问有多少种不同的 n，使得n 不是 3 的倍数？
由于结果可能非常大，请输出对 1000000007 取模的结果。

输入描述:

第一行包含一个正整数 n（1 \leq n \leq 10^{200000}）。
数据保证最初生成的 n 不含前导 0。

输出描述:

输出一行，代表对 1000000007 取模后的结果。
示例1

输入

复制 
1234

输出

复制 
10

说明

样例 1 中，合法结果有：1234，134，124，13，14，23，34，1，2，4。
示例2

输入

复制 
114514

输出

复制 
27