Contest Duration: - (local time) (100 minutes) Back to Home
E - Distance on Large Perfect Binary Tree /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

2^N-1 頂点からなる木があります。

• 頂点 i と頂点 2i を結ぶ無向辺
• 頂点 i と頂点 2i+1 を結ぶ無向辺

が存在します。これら以外の辺はありません。

2 頂点間の距離を、その 2 頂点を結ぶ単純パスに含まれる辺の個数とします。

### 制約

• 2 \leq N \leq 10^6
• 1 \leq D \leq 2\times 10^6
• 入力に含まれる値は全て整数である

N D

3 2

14

14142 17320

### 出力例 2

11284501

Score : 500 points

### Problem Statement

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 2i,
• an undirected edge connecting Vertex i and Vertex 2i+1.

There is no other edge.

Let the distance between two vertices be the number of edges in the simple path connecting those two vertices.

Find the number, modulo 998244353, of pairs of vertices (i, j) such that the distance between them is D.

### Constraints

• 2 \leq N \leq 10^6
• 1 \leq D \leq 2\times 10^6
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N D

3 2

### Sample Output 1

14

The following figure describes the given tree.

There 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