問題文

英小文字のみからなる、長さ 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 は英小文字のみからなる

入力例 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 で割った余りを出力してください。