题目描述

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

在将每个?替换为一个数字之后得到的整数中，有多少个除以 13 的余数为 5?一个整数可能以 0开始。

由于答案可能很大，将计数结果对 $10^9+7$取模后输出。

输出

输入一个字符串$S$

输出

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

??2??5

768

样例解释

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

?44

1

样例解释

只有 044满足条件。

7?4

0

样例解释

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

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

153716888

提示

字符串$S$中只包含数字字符和?

$1 \leq |S| \leq 10^5$