分数: 200 点
问题陈述
给你一个字符串 S 长度 N。 在其子序列中,计算所有字符都不同的子序列,模数 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,两次出现 ba。请注意,我们不计算 baa,因为它包含两个 as。
示例输入 3
5 abcab
示例输出 3
17