問題一覧 > 通常問題

No.3515 Anti EIKO

レベル : / AI推定難易度 : 1925 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 38
作問者 : GaLLium / テスター : Yoyoyo8128 aa36 imabc yu23578 Germanium32 yt142857
お気に入りにしたユーザー ProblemId : 13127 / 自分の提出
問題文最終更新日: 2026-04-30 12:22:04
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 497 聖光学院プログラミングコンテスト2026 day1 (順位表) の他の問題:

Problem Statement

Initially, Hijiri has a string of length $4N$, $T=$ SSSSS...SSSSS, and he repeats the following operation until he faints.

  • Delete $1$ character from the beginning of $T$, then choose $1$ character at random from the $5$ kinds of characters S,E,I,K,O and append it to the end of $T$. Here, each character is always chosen with probability $\dfrac{1}{5}$. When $T$ becomes the string formed by concatenating $N$ copies of the string EIKO, Hijiri faints.
Find the probability, modulo $\bmod 998244353$, that the number of operations performed until Hijiri faints is exactly $K$.

About probability $\bmod 998244353$

Under the constraints of this problem, the probability to be found is always a rational number $Q$, and there exists a pair of integers $(X,Y) (X \not\equiv 0 \pmod{998244353})$ satisfying $XQ=Y$. Then there is a unique integer $Z$ such that $0 \leq Z \lt 998244353$ and $XZ \equiv Y \pmod{998244353}$, so output that value.

Constraints

  • All input values are integers.
  • $1 \leq N \leq 25$
  • $1 \leq K \leq 10^{18}$

Input

$N\ K$

Output

Output the answer on $1$ line.

Sample

Sample 1
Input
1 4
Output
771443236

The condition is satisfied only when E,I,K,O are chosen in the $1,2,3,4$-th operations, respectively. The probability is $\dfrac{1}{625}$. Note that you must output it modulo $\bmod 998244353$.

Sample 2
Input
2 7
Output
0

The probability may be $0$. After $7$ operations, the string he remembers can never be EIKOEIKO.

Sample 3
Input
19 123456789
Output
646671269

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