题目背景

Xudongning 有一个非空字符串 $S$，其中只有数字字符。

Xudongning 又得到了一个空字符串 $T$。

题目描述

Xudongning 每轮向 $T$ 末尾等概率添加任意一个数字字符。当 $S$ 成为 $T$ 的后缀时，就停止添加。

求 Xudongning 添加字符的期望轮数，对 $10^9 + 7$ 取模。

输入格式

仅一行，字符串 $S$。

输出格式

一个整数，表示 Xudongning 添加字符的期望轮数，对 $10^9 + 7$ 取模。

输入输出样例 #1

输入 #1

12

输出 #1

100

说明/提示

$1\le |S| \le 10^6.$