/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2^N-1 頂点からなる木があります。
頂点には 1 から 2^N-1 の番号がつけられており、各 1\leq i < 2^{N-1} について、
- 頂点 i と頂点 2i を結ぶ無向辺
- 頂点 i と頂点 2i+1 を結ぶ無向辺
が存在します。これら以外の辺はありません。
2 頂点間の距離を、その 2 頂点を結ぶ単純パスに含まれる辺の個数とします。
頂点の組 (i,j) であって、距離が D であるようなものの個数を 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 10^6
- 1 \leq D \leq 2\times 10^6
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N D
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
14
与えられる木は以下の図のようなものです。
距離が 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) の 14 組存在します。
入力例 2
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
Output
Print the answer.
Sample Input 1
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).
Sample Input 2
14142 17320
Sample Output 2
11284501