No.840 ほむほむほむら
レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 83
作問者 :
tempura_pp
/ テスター :
keymoon
タグ : / 解いたユーザー数 83
作問者 :
tempura_pp
/ テスター :
keymoon
問題文最終更新日: 2019-06-13 00:15:52
問題文
てんぷらはほむちゃんが好きです。あと $K$ の倍数も好きです。
以下の条件をみたす長さ $N$ の文字列 $S$ の個数を $998244353$ で割った余りを求めてください。
- 「ほ」「む」「ら」以外の文字を含まない。
- $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
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。