{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$t$"},{"iden":"sample input 1","content":"2\nkey"},{"iden":"sample output 1","content":"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`."},{"iden":"sample input 2","content":"2\nccc"},{"iden":"sample output 2","content":"0\n\n*   There are zero ways to choose the positions at which we delete the characters so that $s^{\\prime}=$ `ccc`."},{"iden":"sample input 3","content":"100\nkeyneeneeeckyycccckkke"},{"iden":"sample output 3","content":"275429980\n\n*   Be sure to find the count modulo $998244353$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}