Subsequences of Subsequences

You are given a string s composed of lowercase Latin letters. Your task is to determine the number of good non-empty subsequences within this string.

A subsequence is defined as good if every one of its non-empty subsequences is a palindrome.

Two subsequences are considered distinct if they are derived by removing characters at different indices. This means that even if the resulting subsequences are identical in terms of characters, they are considered different if the indices of the removed characters differ.

Input Format

The first line contains the string s (1 ≤ |s| ≤ 10^5), where all characters are lowercase Latin letters.

Output Format

Output a single integer — the count of good non-empty subsequences of the string s, taken modulo 10^9 + 7 (1000000007).

Examples

Note

In the first example, there are 4 good subsequences: "a", "b", "c", "d".