题目描述

给定一个字符串$S$，其中每个字符是数字(0~9)或?。

将所有的?替换为数字后，能组成多少个被$13$除余$5$的整数？允许数字以$0$开头。

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

输入格式

输入格式如下

$S$

输出格式

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

样例 #1

输入

??2??5

输出

768

样例 #2

输入

?44

输出

1

样例 #3

输入

7?4

输出

0

样例 #4

输入

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

输出

153716888

提示

数据范围

• $S$由数字(0~9)和?组成
• $1 \leq |S| \leq 10^5$

样例1说明

例如$482305$、$002865$、$972665$等都满足条件。

样例2说明

只有$044$满足条件。

样例3说明

有时可能无法构造出满足条件的整数。