問題文

英小文字と ? からなる長さ $N$ の文字列 $S$ が与えられます。

$S$ の空でない部分列は $2^{N}-1$ 個ありますが、その部分列のうち以下のいずれかの条件を満たすものを良い部分列と定義します。

条件

• 部分列に ? が含まれない

• 部分列に ? が1つだけ含まれる

ここで、文字列 yukicoder のうち1文字以下を選び ? に置き換えた文字列の集合を $T$ とします。

良い部分列のうち $T$ に含まれる部分列の個数を $10^9+7$ で割った余りを求めてください。

入力

$N$
$S$

• 1行目に整数 $N$ が与えられる

• 2行目に文字列 $S$ が与えられる

制約

• $1≤N≤10^5$

• $N$ は整数である

• $|S|=N$

• $S$ は英小文字または ? からなる

出力

答えを1行に出力してください。

最後に改行してください。

サンプル

9
yukicoder

1

7
harurun

0

14
yukiyuki?coder

14