题目描述

给定一个长度为 $N$ 的字符串 $S$。请你求出 $S$ 的所有子序列中，仅由互不相同的字符组成的子序列的个数，并对 $10^9+7$ 取模后输出。需要注意的是，即使子序列的字符串内容相同，只要它们取自不同的位置，也要分别计数。

这里，字符串的子序列指的是从原字符串中取出若干（至少一个）字符，并保持原有顺序连接而成的字符串。

输入格式

输入通过标准输入按以下格式给出。

$N$ $S$

输出格式

输出仅由不同字符组成的子序列的个数，对 $10^9+7$ 取模后的结果。

样例 1

输入

4
abcd

输出

15

样例 2

输入

3
baa

输出

5

样例 3

输入

5
abcab

输出

17

说明/提示

限制条件

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

样例解释 1

$S$ 本身所有字符都不同，因此所有子序列都满足条件。

样例解释 2

b、a（有 $2$ 种）、ba（有 $2$ 种），总共 $5$ 种是答案。像 baa 这样的子序列由于包含了 $2$ 个 a，不符合条件。

由 ChatGPT 4.1 翻译