← 返回题目列表

AtCoder · typical90_h

008. 柜台处(★4)

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

配点: 4 点

問題文

仅由小写字母组成的长度 N 字符串 S 。S 的 i 第一个字母 如何提取超过 s_i 。

S 从 0 字符 2^{N} 方法有很多,但满足以下条件的有多少呢?答案可能很大,所以答案是 10^9 + 7 后的余数。

  • 通过组合提取的字符而不改变顺序而创建的字符串变为“atcoder”

然而,“提取字符的方法”仅限于仅从一侧提取的字符。 如果至少存在一个,则区分 s_i (1 \leq i \leq N)。

制約

  • 1 \leq N \leq 100{,}000
  • |S| = N
  • 文字列 S 仅由小写字母组成

入力

输入是按以下格式从标准输入给出的。

N
S

出力

答案 10^9 + 7 后的余数。


入力例 1

10
attcordeer

出力例 1

4

作为“atcoder”子序列的示例, 一种可能性是使用第S 的 (1, 2, 4, 5, 7, 8, 10) 个字符。还有其他满足条件的子序列。 3 存在,所以答案是 4 是的。


入力例 2

41
btwogablwetwoiehocghiewobadegwhoihegnldir

出力例 2

2

入力例 3

140
aaaaaaaaaaaaaaaaaaaattttttttttttttttttttccccccccccccccccccccooooooooooooooooooooddddddddddddddddddddeeeeeeeeeeeeeeeeeeeerrrrrrrrrrrrrrrrrrrr

出力例 3

279999993

10^9 + 7 后的余数。