Expected Usable Bot Binary Strings

A bot named H is given a fixed sequence \(\{A_i\}_{i=1}^{n}\) where each \(A_i\) is chosen uniformly at random from \([0,2^k-1]\) and a binary string \(H\) of length \(n\) (each character is either \(0\) or \(1\)). For any query on an interval \([l,r]\) (with \(1 \le l \le r \le n\)), the bot must provide the set

[ g(l,r)={B_l \oplus B_{l+1},;B_{l+1} \oplus B_{l+2},;\ldots,;B_{r-1} \oplus B_r}, ]

where the sequence \(\{B_i\}_{i=1}^{n}\) is defined as follows for each \(1\le i\le n\):

• If \(H_i = 0\), then \(B_i = A_i\) (the bot cannot change this value).
• If \(H_i = 1\), the bot can choose any nonnegative integer \(v\) and set \(B_i = v\) (the new value can be any nonnegative integer, not necessarily in \([0,2^k-1]\)).

Miaozai NiuNai performs several tests on the bot. In each test, two intervals \([l,r]\) and \([L,R]\) are chosen with \(r \le L\). The bot is asked to provide \(g(l,r)\) and \(g(L,R)\). If the two sets have any common element (i.e. \(g(l,r) \cap g(L,R) \neq \varnothing\)), then the test fails and the bot’s true identity is revealed.

The bot is said to be safe for a given binary string \(H\) if there is a strategy (i.e. a way to choose the values for all \(B_i\) with \(H_i = 1\) on every query) such that for every possible pair of intervals (with \(r\le L\)) the two sets do not have any common element. In other words, if the bot can always answer without causing a detection failure, the string \(H\) is usable.

It turns out that the only potential danger comes from those indices where the bot has no control: if two adjacent indices are both forced (i.e. when \(H_i = H_{i+1} = 0\)), the corresponding value \(B_i \oplus B_{i+1} = A_i \oplus A_{i+1}\) is fixed and then could appear in the answers for two different queries simultaneously. Therefore, a necessary and sufficient condition for \(H\) to be usable is that no two consecutive characters are both \(0\).

Given that the random sequence \(\{A_i\}\) does not affect the usability when \(H\) has no adjacent zeros, the expected number of usable binary strings \(H\) is simply the number of binary strings of length \(n\) that do not contain "00" as a substring. It is well known that if we denote by \(f(n)\) the number of such strings, then:

[ f(1)=2,\quad f(2)=3,\quad f(n)=f(n-1)+f(n-2) \quad \text{for } n\ge 3. ]

Observing that \(f(n)\) coincides with the Fibonacci sequence shifted by two positions (i.e. \(f(n)=F_{n+2}\) with the standard Fibonacci numbers defined by \(F_0=0, F_1=1\)), your task is to compute the expected number of usable binary strings \(H\) modulo \(998244353\).

Input: Two integers \(n\) and \(k\). Note that \(k\) does not affect the answer.

Output: Output one integer, the number of usable binary strings modulo \(998244353\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(k\) separated by a space.

\(1 \le n \le 10^{12}\) (potentially large) and \(k\) is a positive integer.

outputFormat

Output a single integer: the number of usable binary strings modulo \(998244353\).

sample

1 1

2