No.840 ほむほむほむら

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 56
作問者 : tempura_pptempura_pp / テスター : keymoonkeymoon
1 ProblemId : 2892 / 出題時の順位表

問題文

てんぷらはほむちゃんが好きです。あと $K$ の倍数も好きです。
以下の条件をみたす長さ $N$ の文字列 $S$ の個数を $998244353$ で割った余りを求めてください。

  1. 「ほ」「む」「ら」以外の文字を含まない。
  2. $S$ のほむ度が $K$ の倍数である。 ただし「ほむ度」とは以下の条件をすべてみたす整数 $(i,\ j,\ k)$ の組の個数のことを言う。
    • $1\le i < j < k \le N$
    • $S_i$($S$の$i$文字め) $=$「ほ」
    • $S_j\ =$「む」
    • $S_k\ =$「ら」

入力

$N\ K$

  • $1\le N\le 10^9$
  • $2\le K\le 5$
  • 入力はともに整数

出力

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

サンプル

サンプル1
入力
4 2
出力
75

例えば「ほむらら」や「ほむほむ」はほむ度がそれぞれ2, 0なので条件をみたします。 「ほらむら」はほむ度が1なのでダメです。

サンプル2
入力
7 4
出力
1430

「ほむほむほむら」のほむ度は6です。

サンプル3
入力
31415926 5
出力
753660663

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。