题目描述

Bob 最近对切绳子问题很感兴趣，一根绳子对折 $1$ 次，从中间切 $1$ 刀，绳子会变成 $3$ 段。如果对折 $2$ 次，从中间切 $1$ 刀绳子变为 $5$ 段,如果切 $2$ 刀，绳子会变为 $9$ 段。

依次类推，一根绳子对折 $n$ 次，从中间切 $k$ 刀，最后会有多少段？ 答案取 $10^9+7$ 的余数。

输入格式

两个整数 $n$ $k$

输出格式

一个整数，表示对折 $n$ 次切 $k$ 刀绳子的段数取 $10^9+7$ 的余数。

1 1

3

2 2

9

10 3

3073

0 3

4

100000 3

823170554

数据规模与约定

$Subtask1$: $0\le n,k \le 20$ , $20$ 分

$Subtask2$: $0\le n,k \le 10^5$ , $40$ 分

$Subtask3$: $0\le n,k \le 10^{18}$ , $40$ 分