Equal Digits

Time limit3sMemory limit256 MB

Summary

Count the ways to delete disjoint substrings of length over 1 whose first and last digits match, so the remaining non-empty string has all distinct digits.

Level: Medium7 of 10
Topics: Dynamic programming, Combinatorics, String, Prefix sum
Solved: No attempts yet

Problem

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$ .

Input

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

Output

Output one integer: the answer to the problem.

Examples2

Example 1
Input
```
88005553535
```
Expected output
```
7
```
Example 2
Input
```
123
```
Expected output
```
1
```