Problem 774

Conjunctive Sequences

$&$ denote the bitwise AND operation.

For example, $10 & 12 = 1010_{2} & 1100_{2} = 1000_{2} = 8$ .

We shall call a finite sequence of non-negative integers $(a_{1}, a_{2}, \dots, a_{n})$ conjunctive if $a_{i} & a_{i + 1} \neq 0$ for all $i = 1 \dots n - 1$ .

Define $c (n, b)$ to be the number of conjunctive sequences of length $n$ in which all terms are $\leq b$ .

You are given that $c (3, 4) = 18$ , $c (10, 6) = 2496120$ , and $c (100, 200) \equiv 268159379 (\mod 998244353)$ .

Find $c (123, 123456789)$ . Give your answer modulo $998244353$ .

合取数列

$&$ 表示按位与操作。

例如， $10 & 12 = 1010_{2} & 1100_{2} = 1000_{2} = 8$ 。

若有限非负整数列 $(a_{1}, a_{2}, \dots, a_{n})$ 满足，对所有 $i = 1 \dots n - 1$ 均有 $a_{i} & a_{i + 1} \neq 0$ ，则称之为合取数列。

记 $c (n, b)$ 为所有长度为 $n$ 且各项均 $\leq b$ 的合取数列的数目。

已知 $c (3, 4) = 18$ ， $c (10, 6) = 2496120$ ，以及 $c (100, 200) \equiv 268159379 (\mod 998244353)$ 。

求 $c (123, 123456789)$ ，并将你的答案对 $998244353$ 取余。