{"problem":{"name":"Distance on Large Perfect Binary Tree","description":{"content":"We have a tree with $2^N-1$ vertices.   The vertices are numbered $1$ through $2^N-1$. For each $1\\leq i < 2^{N-1}$, the following edges exist: *   an undirected edge connecting Vertex $i$ and Vertex","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc220_e"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $2^N-1$ vertices.  \nThe vertices are numbered $1$ through $2^N-1$. For each $1\\leq i < 2^{N-1}$, the following edges exist:\n\n*   an undirected edge connecting Vertex $i$ and Vertex $2i$,\n*   an undirected edge connecting Vertex $i$ and Vertex $2i+1$.\n\nThere is no other edge.\nLet the distance between two vertices be the number of edges in the simple path connecting those two vertices.\nFind the number, modulo $998244353$, of pairs of vertices $(i, j)$ such that the distance between them is $D$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^6$\n*   $1 \\leq D \\leq 2\\times 10^6$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $D$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc220_e","tags":[],"sample_group":[["3 2","14\n\nThe following figure describes the given tree.\n![image](https://img.atcoder.jp/ghi/86d098048a50638decb39ed6659d32cf.png)\nThere are $14$ pairs of vertices such that the distance between them is $2$: $(1,4),(1,5),(1,6),(1,7),(2,3),(3,2),(4,1),(4,5),(5,1),(5,4),(6,1),(6,7),(7,1),(7,6)$."],["14142 17320","11284501"]],"created_at":"2026-03-03 11:01:14"}}