{"raw_statement":[{"iden":"problem statement","content":"$NK$ people are standing in a line from left to right. Let us denote them as person $i$ $(0\\leq i \\leq NK-1)$ from left to right.\nEach person is always facing either left or right. The direction of each person at time $t=0$ is represented by a string of length $N$, $S=S_0 S_1 \\dots S_{N-1}$, consisting of `L` and `R`. At time $t=0$, person $i$ is facing left if $S_{i \\bmod N}$ is `L`, and right if it is `R`.\nAt time $t=0.5,\\ 1.5,\\ 2.5 ,\\ \\dots$, these people **simultaneously** change their directions according to the following rules.\n\n*   When a person is facing left:  \n    If there are one or more people in the direction the person is facing, and more than half of those people are facing right, the person changes direction and faces right. Otherwise, the person does not change direction.\n*   When a person is facing right:  \n    If there are one or more people in the direction the person is facing, and more than half of those people are facing left, the person changes direction and faces left. Otherwise, the person does not change direction.\n\nFind the sum, modulo $998244353$, of the numbers of times the $NK$ people change direction from time $t=0$ to $t=10^{100}$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq K \\leq 2 \\times 10^5$\n*   $S$ is a string of length $N$ consisting of `L` and `R`.\n*   All numerical values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $K$\n$S$"},{"iden":"sample input 1","content":"7 1\nRRLRLLL"},{"iden":"sample output 1","content":"9\n\nIf we represent the directions of the seven people at each time, we have `LLRLRRL` at $t=1$, `LLRLRLL` at $t=2$, and `LLLLLLL` at $t=3$.\nAfter $t=3$, the directions of the seven people do not change. Therefore, the answer is $1+1+2+1+2+2+0=9$."},{"iden":"sample input 2","content":"4 10\nLLRR"},{"iden":"sample output 2","content":"0"},{"iden":"sample input 3","content":"23 200\nRLRRRLLLLLLLLRRRLLRLRRR"},{"iden":"sample output 3","content":"2207"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}