{"problem":{"name":"Division by Two with Something","description":{"content":"Given are integers $N$ and $X$. For each integer $k$ between $0$ and $X$ (inclusive), find the answer to the following question, then compute the sum of all those answers, modulo $998244353$. *   Let","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc039_c"},"statements":[{"statement_type":"Markdown","content":"Given are integers $N$ and $X$. For each integer $k$ between $0$ and $X$ (inclusive), find the answer to the following question, then compute the sum of all those answers, modulo $998244353$.\n\n*   Let us repeat the following operation on the integer $k$. Operation: if the integer is currently odd, subtract $1$ from it and divide it by $2$; otherwise, divide it by $2$ and add $2^{N-1}$ to it. How many operations need to be performed until $k$ returns to its original value? (The answer is considered to be $0$ if $k$ never returns to its original value.)\n\n## Constraints\n\n*   $1 \\leq N \\leq 2\\times 10^5$\n*   $0 \\leq X < 2^N$\n*   $X$ is given in binary and has exactly $N$ digits. (In case $X$ has less than $N$ digits, it is given with leading zeroes.)\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$X$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc039_c","tags":[],"sample_group":[["3\n111","40\n\nFor example, for $k=3$, the operation changes $k$ as follows: $1,0,4,6,7,3$. Therefore the answer for $k=3$ is $6$."],["6\n110101","616"],["30\n001110011011011101010111011100","549320998"]],"created_at":"2026-03-03 11:01:14"}}