Counting Subsequence with Same Character Frequency

You are given a string word. Count the number of subsequences of word such that every character that appears in the subsequence appears the same number of times. Return this count modulo 10^9 + 7.

Input

• word: a string made up of lowercase English letters. Its length is at most 1000.

Output

• The number of valid subsequences, computed modulo 10^9 + 7.

Example

Input: word = "aaa"
Output: 8

Explanation

Because "aaa" uses only the letter 'a', every subsequence has all of its characters occurring the same number of times. The subsequences are the empty string, three single-letter subsequences, three two-letter subsequences, and "aaa", for a total of 8.