题目描述

给定一个字符串 $s$，$s$ 仅包含数字和下划线。小爱需要将所有下划线填成数字，使得整个字符串组成的数字是 $13$ 的倍数，请统计有多少种填充方法。首位可以填 $0$。

输入格式

单个字符串 $s$

输出格式

单个整数，表示符合条件的方案数，由于满足条件的方案可能较多，输出答案模 $10^9+7$ 的余数。

1_7

1

样例解释 1

填充方案共1种，117。

_3_

8

数据范围

记 $n$ 表示输入字符串 $s$ 的长度，则

• 对于 $30\%$ 的数据，$1\leq n \leq 10$；
• 对于 $60\%$ 的数据，$1\leq n \leq 1000$；
• 对于 $100\%$ 的数据，$1\leq n \leq 100,000$。