该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

总所周知，石老板终身未娶。他在婚姻介绍所门口，捡到了一张小纸条，上面写很长一串很长的十进制数 $s$。

对着这个数字串，石老板陷入幻想：

他拥有的金钱是 $s$ 的任意一个非空子序列，比如 $s=114514$，那么 $154$ 就可能是一个金钱数。

现在他有三个老婆，他必须把钱到给上交上去。其中有一个是正妻因为需要母仪天下，所以他的金钱不能是 $3$ 的倍数（正妻要多分一点）。

那么有哪些不同的 $s$ 子序列满足这个要求呢？注意金钱数不能有前导 $0$ 。

输入格式

一个数字串 $s$。

输出格式

一个整数，表示答案对 $10^9+7$ 取模的结果。

样例输入 1

1818

样例输出 1

8

样例解释

$1,8,11,88,181,188,118,818$ 都是可能的金钱数。

样例输入 2

43005300951655298892

样例输出 2

121860

数据范围与提示

对于 $30\%$ 的数据，满足 $|s|\le 20$。

对于 $100$ 的数据，满足 $|s|\le 10^6$ ，且 $s$ 仅包含 $0\sim9$ 的数字。