{"problem":{"name":"Ex - Fibonacci: Revisited","description":{"content":"We define the general term $a_n$ of a sequence $a_0, a_1, a_2, \\dots$ by: $a_n = \\begin{cases} 1 & (0 \\leq n \\lt K) \\\\ \\displaystyle{\\sum_{i=1}^K} a_{n-i} & (K \\leq n). \\\\ \\end{cases}$    Given an ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":6000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc300_h"},"statements":[{"statement_type":"Markdown","content":"We define the general term $a_n$ of a sequence $a_0, a_1, a_2, \\dots$ by:\n\n$a_n = \\begin{cases} 1 & (0 \\leq n \\lt K) \\\\ \\displaystyle{\\sum_{i=1}^K} a_{n-i} & (K \\leq n). \\\\ \\end{cases}$\n\n  \n\nGiven an integer $N$, find the sum, modulo $998244353$, of $a_m$ over all non-negative integers $m$ such that $m\\text{ AND }N = m$. ($\\text{AND}$ denotes the bitwise AND.)\nWhat is bitwise AND? The bitwise AND of non-negative integers $A$ and $B$, $A\\text{ AND }B$, is defined as follows.  \n・When $A\\text{ AND }B$ is written in binary, its $2^k$s place ($k \\geq 0$) is $1$ if $2^k$s places of $A$ and $B$ are both $1$, and $0$ otherwise.\n\n## Constraints\n\n*   $1 \\leq K \\leq 5 \\times 10^4$\n*   $0 \\leq N \\leq 10^{18}$\n*   $N$ and $K$ are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$K$ $N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc300_h","tags":[],"sample_group":[["2 6","21\n\n$a_0$ and succeeding terms are $1, 1, 2, 3, 5, 8, 13, 21, \\dots$. Four non-negative integers, $0, 2, 4$, and $6$, satisfy $6 \\text{ AND } m = m$, so the answer is $1 + 2 + 5 + 13 = 21$."],["2 8","35"],["1 123456789","65536"],["300 20230429","125461938"],["42923 999999999558876113","300300300"]],"created_at":"2026-03-03 11:01:14"}}