← 返回题目列表

AtCoder · agc031_a

A. 彩色子序列

中文机器翻译题面 查看原题

分数: 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