Connected Subtree Coloring in Complete Binary Trees

Little C has a complete binary tree of dep levels with n nodes. She wants to choose a connected subset (i.e. a connected subgraph) of nodes which must include the root and color them. Two colorings are considered different if the set of colored nodes differ. Find the number of different coloring schemes modulo \(998{,}244{,}353\).

Note: Please pay attention to the unusual time limit.

Definition: In a tree, any connected subset containing the root has the property that for each node included, all nodes on the unique path from the root to that node are also included.

Hint: If you denote by \(f(u)\) the number of ways to choose a connected subset in the subtree rooted at \(u\) (with \(u\) included), then for each child \(v\) of \(u\), you have two options: either do not include any node from the subtree of \(v\) or include a connected subset including \(v\); therefore, \(f(u)=\prod_{v\text{ child of }u}(1+f(v))\). The answer is \(f(root)\).

inputFormat

The input consists of a single line containing two integers, dep and n, where:

• dep is the number of levels in the complete binary tree.
• n is the total number of nodes in the tree (the tree is formed by taking the first n nodes in level‐order from a complete binary tree of dep levels).

You can assume that \(1 \leq n \leq 2^{dep}-1\).

outputFormat

Output a single integer: the number of different connected colorings (i.e. connected subtrees including the root), taken modulo \(998{,}244{,}353\).

sample

3 3

4