/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
長さ N の文字列 S が与えられます。 S の部分列であって、すべて異なる文字からなるものの数を 10^9+7 で割った余りを答えてください。文字列として同一でも、異なる位置から取り出された部分列は区別して数えることとします。
ただし、文字列の部分列とは、文字列から文字をいくつか 正の個数 取り出し、もとの文字列から順序を変えずにつなげたものを指します。
制約
- 1 \leq N \leq 100000
- S は英小文字からなる
- |S|=N
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
異なる文字からなる部分列の個数を 10^9+7 で割った余りを出力せよ。
入力例 1
4 abcd
出力例 1
15
S 自体がすべて異なる文字からなるので、すべての部分列が条件を満たします。
入力例 2
3 baa
出力例 2
5
b, a (2 通り), ba (2 通り) の合計 5 通りが答えとなります。baa などはaが 2 回現れるため当てはまらないことに注意してください。
入力例 3
5 abcab
出力例 3
17
Score : 200 points
Problem Statement
You are given a string S of length N. Among its subsequences, count the ones such that all characters are different, modulo 10^9+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.
Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.
Constraints
- 1 \leq N \leq 100000
- S consists of lowercase English letters.
- |S|=N
Input
Input is given from Standard Input in the following format:
N S
Output
Print the number of the subsequences such that all characters are different, modulo 10^9+7.
Sample Input 1
4 abcd
Sample Output 1
15
Since all characters in S itself are different, all its subsequences satisfy the condition.
Sample Input 2
3 baa
Sample Output 2
5
The answer is five: b, two occurrences of a, two occurrences of ba. Note that we do not count baa, since it contains two as.
Sample Input 3
5 abcab
Sample Output 3
17