题目描述

给定一个字符串 $S$。$S$ 中的每个字符都是数字 (0, ..., 9) 或者 ?。

当用一个数字替换掉 $S$ 中的每个 ?，得到的整数中有多少个整数除以 $13$ 的余数是 $5$？一个整数可以以 $0$ 开头。

由于答案可能非常大，输出答案对 $10^9+7$ 取模的结果。

约束条件

• $S$ 是一个只包含数字 (0, ..., 9) 和 ? 的字符串。
• $1 \\leq |S| \\leq 10^5$

输入

从标准输入读入输入数据。

输入数据的格式如下：

$S$

输出

输出满足条件的整数的个数，对 $10^9+7$ 取模。

示例输入 1

??2??5

示例输出 1

768

例如，$482305, 002865$ 和 $972665$ 满足条件。

示例输入 2

?44

示例输出 2

1

只有 $044$ 满足条件。

示例输入 3

7?4

示例输出 3

0

我们可能无法得到满足条件的整数。

示例输入 4

?6?42???8??2??06243????9??3???7258??5??7???????774????4?1??17???9?5?70???76???

示例输出 4

153716888