[HNOI2002]跳蚤

Z 城市里居住着许多跳蚤。当地周六生活频道有一档娱乐节目：一只跳蚤会被放在一根高空钢丝的正中央。钢丝足够长，可以视为无限长。

节目主持人会给跳蚤一张卡片，卡片上依次写有 $N+1$ 个自然数。最后一个数固定为 $M$ ，前 $N$ 个数均不超过 $M$ ，并且允许出现相同的数。

每次跳跃时，跳蚤可以从卡片上任意选择一个数 $S$ ，向左或向右跳 $S$ 个单位长度。同一个数可以被选择任意多次。跳蚤的任务是最终到达初始位置左侧 $1$ 个单位长度处，并捡起那里的礼物。

例如，当 $N=2$ 、 $M=18$ 时，持有卡片 $(10,15,18)$ 的跳蚤可以先向左跳 $10$ 个单位长度，再连续向左跳 $3$ 次，每次跳 $15$ 个单位长度，最后连续向右跳 $3$ 次，每次跳 $18$ 个单位长度，从而完成任务。而持有卡片 $(12,15,18)$ 的跳蚤无论如何也无法到达目标位置。

给定 $N$ 和 $M$ ，共有 $M^N$ 张不同的卡片。请计算其中有多少张卡片能使跳蚤完成任务。

输入格式

输入仅一行，包含两个以空格分隔的整数 $N$ 和 $M$ 。

输出格式

输出仅一行，包含一个整数，表示能够使跳蚤完成任务的卡片数量。

样例输入

2 4

样例输出

数据范围

$1\le N\le 15$ ；
$1\le M\le 10^8$ ；
对于卡片上的前 $N$ 个数，均满足 $1\le a_i\le M$ ；
答案可能超过 $64$ 位整数的表示范围，需要使用高精度整数。

来源与许可

本题为 HNOI 2002 试题「跳蚤」，题面与测试数据整理自 BZOJ。

样例 1

输入

2 4