#agc031a. [agc031_a]Colorful Subsequence

[agc031_a]Colorful Subsequence

问题描述

给定长度为 NN 的字符串 SS。在其子序列中,计算满足所有字符都不同的子序列的数量,并对 109+710^9 + 7 取模。如果两个子序列的字符来自字符串的不同位置,即使它们是相同的,也认为它们是不同的子序列。

这里,字符串的子序列是从字符串中选择一个或多个字符并按原始顺序连接起来得到的。

约束条件

  • 1N1000001 \leq N \leq 100000
  • SS 由小写英文字母组成。
  • S=N|S|=N

输入

输入通过标准输入给出,格式如下:

NN SS

输出

打印满足所有字符都不同的子序列的数量,对 109+710^9 + 7 取模。


示例输入 1

4
abcd

示例输出 1

15

由于 SS 中的所有字符都不同,因此它的所有子序列都满足条件。


示例输入 2

3
baa

示例输出 2

答案是五:b,两个 a,两个 ba。请注意,我们不计算 baa,因为它包含两个 a


示例输入 3

5
abcab

示例输出 3

17