{"problem":{"name":"Increasing Prefix XOR","description":{"content":"You are given positive integers $N$ and $M$. Find the number of sequences $A=(A_1,\\ A_2,\\ \\dots,\\ A_N)$ of $N$ positive integers that satisfy the following conditions, modulo $998244353$. *   $1 \\leq","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc141_b"},"statements":[{"statement_type":"Markdown","content":"You are given positive integers $N$ and $M$.\nFind the number of sequences $A=(A_1,\\ A_2,\\ \\dots,\\ A_N)$ of $N$ positive integers that satisfy the following conditions, modulo $998244353$.\n\n*   $1 \\leq A_1 < A_2 < \\dots < A_N \\leq M$.\n*   $B_1 < B_2 < \\dots < B_N$, where $B_i = A_1 \\oplus A_2 \\oplus \\dots \\oplus A_i$.\n\nHere, $\\oplus$ denotes bitwise $\\mathrm{XOR}$.\nWhat is bitwise $\\mathrm{XOR}$?The bitwise $\\mathrm{XOR}$ of non-negative integers $A$ and $B$, $A \\oplus B$, is defined as follows:\n\n*   When $A \\oplus B$ is written in base two, the digit in the $2^k$'s place ($k \\geq 0$) is $1$ if exactly one of $A$ and $B$ is $1$, and $0$ otherwise.\n\nFor example, we have $3 \\oplus 5 = 6$ (in base two: $011 \\oplus 101 = 110$).  \nGenerally, the bitwise $\\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \\dots, p_k$ is defined as $(\\dots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\dots \\oplus p_k)$. We can prove that this value does not depend on the order of $p_1, p_2, p_3, \\dots, p_k$.\n\n## Constraints\n\n*   $1 \\leq N \\leq M < 2^{60}$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc141_b","tags":[],"sample_group":[["2 4","5\n\nFor example, $(A_1,\\ A_2)=(1,\\ 3)$ counts, since $A_1 < A_2$ and $B_1 < B_2$ where $B_1=A_1=1,\\ B_2=A_1\\oplus A_2=2$.\nThe other pairs that count are $(A_1,\\ A_2)=(1,\\ 2),\\ (1,\\ 4),\\ (2,\\ 4),\\ (3,\\ 4)$."],["4 4","0"],["10 123456789","205695670"]],"created_at":"2026-03-03 11:01:14"}}