题目描述

设 $\red{r}$是个 $\red{2^k}$进制数，并满足以下条件：

$\red{（1）}$ $\red{r}$至少是个 $\red{2}$位的 $\red{2^k}$进制数；

$\red{（2）}$作为 $\red{2^k}$进制数，除最后一位外， $\red{r}$的每一位严格小于它右边相邻的那一位；

$\red{（3）}$将 $\red{r}$转换为 $\red{2}$进制数 $\red{q}$后，则 $\red{q}$的总位数不超过 $\red{w}$。

在这里，正整数 $\red{k}$和 $\red{w}$是事先给定的。

问：满足上述条件的不同的r共有多少个？

我们再从另一角度作些解释：设 $\red{S}$是长度为 $\red{w}$的 $\red{01}$字符串（即字符串 $\red{S}$由 $\red{w}$个“$\red{0}$”或“$\red 1$”组成）， $\red{S}$对应于上述条件$\red{（3）}$中的 $\red{q}$。将 $\red{S}$从右起划分为若干个长度为 $\red{k}$的段，每段对应一位 $\red{2^k}$进制的数，如果 $\red{S}$至少可分成 $\red{2}$段，则 $\red{S}$所对应的二进制数又可以转换为上述的 $\red{2^k}$进制数 $\red{r}$。

例：设 $\red{k=3，w=7}$。则 $\red{r}$是个八进制数（$\red{2^3=8}$）。由于 $\red{w=7}$，长度为 $\red{7}$的 $\red{01}$字符串按 $\red{3}$位一段分，可分为 $\red{3}$段（即 $\red{1，3，3}$，左边第一段只有一个二进制位），则满足条件的八进制数有：

$\red{2}$位数：高位为 $\red{1}$： $\red{6}$个（即 $\red{12，13，14，15，16，17}$），高位为 $\red{2}$： $\red{5}$个，…，高位为 $\red{6}$： $\red{1}$个（即 $\red{67}$）。共 $\red{6+5+…+1=21}$个。

$\red{3}$位数：高位只能是 $\red{1}$，第 $\red{2}$位为 $\red{2}$： $\red{5}$个（即 $\red{123，124，125，126，127}$），第 $\red{2}$位为 $\red{3}$： $\red{4}$个，…，第 $\red{2}$位为 $\red{6}$： $\red{1}$个（即 $\red{167}$）。共 $\red{5+4+…+1=15}$个。

所以，满足要求的 $\red{r}$共有 $\red{36}$个。

输入格式

只有 $\red{1}$行，为两个正整数，用一个空格隔开：

$\red{k}$ $\red w$

输出格式

$\red{1}$行，是一个正整数，为所求的计算结果，即满足条件的不同的 $\red{r}$的个数（用十进制数表示）。

要求最高位不得为 $\red{0}$，各数字之间不得插入数字以外的其他字符（例如空格、换行符、逗号等）。

样例

输入样例

3 7

输出样例

36

提示

对于$\red{100\%}$的数据，$\red{1\leq k\leq 9}$，$\red{k<W\leq30,000}$。

（提示：作为结果的正整数可能很大，但不会超过 $\red{200}$位）