E - 大型完全二叉树上的距离

得分：500分

题目描述

我们有一棵包含$2^N-1$个顶点的树。
顶点从$1$到$2^N-1$编号。对于$1\leq i < 2^{N-1}$，存在以下边：

• 连接顶点$i$和顶点$2i$的无向边，
• 连接顶点$i$和顶点$2i+1$的无向边。

没有其他边。

两个顶点之间的距离被定义为连接这两个顶点的简单路径上的边数。

找到满足距离为$D$的顶点对$(i, j)$的数量。

约束条件

• $2 \leq N \leq 10^6$
• $1 \leq D \leq 2\times 10^6$
• 输入的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$N$ $D$

输出

输出答案。

3 2

14

下图描述了给定的树。

有$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)$。

14142 17320

11284501