{"problem":{"name":"popcount <= 2","description":{"content":"You are given positive integers $N,M$. Find the number, modulo $998244353$, of non-negative integer sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ that satisfy all the following conditions. *   $0\\","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc200_e"},"statements":[{"statement_type":"Markdown","content":"You are given positive integers $N,M$.\nFind the number, modulo $998244353$, of non-negative integer sequences $A=(A_1,A_2,\\ldots,A_N)$ of length $N$ that satisfy all the following conditions.\n\n*   $0\\le A_i < 2^M$ $(1\\le i\\le N)$\n*   $\\operatorname{popcount}(A_i\\oplus A_j) \\le 2$ $(1\\le i < j\\le N)$\n\nHere, for non-negative integers $x,y$, we denote by $x\\oplus y$ the bitwise $\\mathrm{XOR}$ operation of $x$ and $y$, and by $\\operatorname{popcount}(x)$ the popcount of $x$.\nYou are given $T$ test cases, so find the answer for each.\nWhat is bitwise $\\mathrm{XOR}$ operation?The bitwise $\\mathrm{XOR}$ of non-negative integers $A, B$, denoted $A \\oplus B$, is defined as follows.\n\n*   When $A \\oplus B$ is written in binary, the digit in the $2^k$ ($k \\geq 0$) place is $1$ if exactly one of $A, B$ has $1$ in the $2^k$ place when written in binary, and $0$ otherwise.\n\nFor example, $3 \\oplus 5 = 6$ (in binary: $011 \\oplus 101 = 110$).\n\nWhat is popcount?For a non-negative integer $x$, $\\operatorname{popcount}(x)$ is the number of $1$s when $x$ is written in binary. More precisely, for a non-negative integer $x$ such that $\\displaystyle x=\\sum _ {i=0} ^ \\infty b _ i2 ^ i\\ (b _ i\\in\\lbrace0,1\\rbrace)$, we have $\\displaystyle\\operatorname{popcount}(x)=\\sum _ {i=0} ^ \\infty b _ i$.\nFor example, $13$ in binary is `1101`, so we have $\\operatorname{popcount}(13)=3$.\n\n## Constraints\n\n*   $1\\le T\\le 2\\times 10^5$\n*   $2\\le N,M < 998244353$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc200_e","tags":[],"sample_group":[["3\n2 3\n7 2\n2025 200","56\n16384\n549499339\n\nConsider the first test case.\nFor example, $A=(4,5)$ satisfies the conditions because each element is between $0$ and $2^3-1=7$, and $\\operatorname{popcount}(4\\oplus 5)=\\operatorname{popcount}(1)=1\\le 2$. On the other hand, neither $A=(2,5)$ nor $A=(0,7)$ satisfies the conditions.\nThere are $56$ sequences $A$ that satisfy the conditions, so output $56$ on the first line."]],"created_at":"2026-03-03 11:01:14"}}