問題一覧 > 通常問題

No.1702 count good string

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 137
作問者 : harurunharurun / テスター : first_vilfirst_vil
2 ProblemId : 6998 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-09-14 13:07:07

問題文

英小文字と ? からなる長さ $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行に出力してください。

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

サンプル

サンプル1
入力
9
yukicoder
出力
1

サンプル2
入力
7
harurun
出力
0

サンプル3
入力
14
yukiyuki?coder
出力
14

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。