{"problem":{"name":"Keyence Repetition","description":{"content":"Let $s$ be the concatenation of $N$ copies of `keyence`. Consider deleting zero or more characters from $s$ and concatenating the remaining characters without changing the order to make a new string $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"keyence2021_f"},"statements":[{"statement_type":"Markdown","content":"Let $s$ be the concatenation of $N$ copies of `keyence`. Consider deleting zero or more characters from $s$ and concatenating the remaining characters without changing the order to make a new string $s^{\\prime}$.\nThere are $2^{7N}$ ways to choose the positions at which we delete the characters. Among them, how many make $s^{\\prime}$ equal to $t$? Find the count modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^{18}$\n*   $1 \\leq |t| \\leq 2.5 \\times 10^5$\n*   $t$ is a string consisting of `c`, `e`, `k`, `n`, and `y`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$t$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"keyence2021_f","tags":[],"sample_group":[["2\nkey","6\n\n*   We have $s=$ `keyencekeyence`.\n*   There are six ways to choose the positions at which we delete the characters so that $s^{\\prime}=$ `key`."],["2\nccc","0\n\n*   There are zero ways to choose the positions at which we delete the characters so that $s^{\\prime}=$ `ccc`."],["100\nkeyneeneeeckyycccckkke","275429980\n\n*   Be sure to find the count modulo $998244353$."]],"created_at":"2026-03-03 11:01:14"}}