#S1033a. 酒杯

酒杯

酒杯(glass)

【题目背景】

快把酒满上干了这杯大声歌唱,我修姚我修姚今宵多欢畅~

某天的凌晨一点,yjt把他的AC装进酒杯里后准备早点睡觉。由于实在是太早了,yjt此时并不急着去洗澡,也不急着刷B站,而是端详起了他的酒杯,此时他惊奇的发现,酒杯的每一层居然都有至少一个AC!yjt感到很不可思议,并想知道这样的概率有多大。

【题目描述】

yjt的酒杯可近似看做一颗深度为n\displaystyle n的满二叉树(根节点深度为1\displaystyle 1),第i\displaystyle i层的大小为 2i1\displaystyle 2^{i-1}。每当A了一道题后,就会有一个AC等概率随机添加到某一个节点上。每个节点可以有大于 1\displaystyle 1 个AC

请问若yjt一共A了 m\displaystyle m 道题,每一层都至少存在一个AC的概率是多少?它想知道这个值乘上 (2n1)m\displaystyle \left( 2^{n} -1\right)^{m} 再对 109+710^9+7 取模后的结果

【输入格式】

一行两个整数 n,m\displaystyle n,m

【输出格式】

一行一个整数 p(0p<109+7)\displaystyle p( 0\leqslant p< 10^9+7),表示答案乘上 (2n1)m\displaystyle \left( 2^{n} -1\right)^{m} 再对 109+710^9+7 取模后的结果

【样例输入1】

3 3

【样例输出1】

48

【样例输入2】

19 26

【样例输出2】

945166646

【样例输入3】

114 514

【样例输出3】

833163249

【数据范围及约定】

数据点编号 nn mm
11 5\le 5
252\sim 5 500\le 500
686\sim 8 20\le 20 =1145141919=1145141919
9209\sim 20 2000\le 2000