시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 0 0 0 0.000%

문제

There is a string $s$ consisting of decimal digits.

You need to transform the string $s$ into any non-empty string $t$ in which all digits are different. To achieve the goal, you can choose and remove a set (possibly empty) of non-intersecting substrings such that the length of each substring is strictly greater than $1$, and in each substring, the first digit is equal to the last one. Find the number of ways to choose such set.

Two sets are different if one of them has a substring that does not exist in the other. Substrings are different if their start or end positions differ.

Since the number of ways can be quite large, output it modulo $10^9 + 7$.

입력

The single line contains the string $s$ ($1 \le |s| \le 10^5$) consisting of decimal digits.

출력

Output one integer: the answer to the problem.

예제 입력 1

88005553535

예제 출력 1

7

예제 입력 2

123

예제 출력 2

1