設(shè)r是個(gè)2^k 進(jìn)制數(shù)，并滿足以下條件：
（1）r至少是個(gè)2位的2^k 進(jìn)制數(shù)。
（2）作為2^k 進(jìn)制數(shù)，除最后一位外，r的每一位嚴(yán)格小于它右邊相鄰的那一位。
（3）將r轉(zhuǎn)換為2進(jìn)制數(shù)q后，則q的總位數(shù)不超過w。
在這里，正整數(shù)k（1≤k≤9）和w（k〈w≤30000）是事先給定的。

問：滿足上述條件的不同的r共有多少個(gè)？
我們?cè)購(gòu)牧硪唤嵌茸餍┙忉專涸O(shè)S是長(zhǎng)度為w 的01字符串（即字符串S由w個(gè)“0”或“1”組成），S對(duì)應(yīng)于上述條件（3）中的q。將S從右起劃分為若干個(gè)長(zhǎng)度為k 的段，每段對(duì)應(yīng)一位2^k進(jìn)制的數(shù)，如果S至少可分成2段，則S所對(duì)應(yīng)的二進(jìn)制數(shù)又可以轉(zhuǎn)換為上述的2^k 進(jìn)制數(shù)r。
例：設(shè)k=3，w=7。則r是個(gè)八進(jìn)制數(shù)（2^3=8）。由于w=7，長(zhǎng)度為7的01字符串按3位一段分，可分為3段（即1，3，3，左邊第一段只有一個(gè)二進(jìn)制位），則滿足條件的八進(jìn)制數(shù)有：
2位數(shù)：高位為1：6個(gè)（即12，13，14，15，16，17），高位為2：5個(gè)，…，高位為6：1個(gè)（即67）。共6+5+…+1=21個(gè)。
3位數(shù)：高位只能是1，第2位為2：5個(gè)（即123，124，125，126，127），第2位為3：4個(gè)，…，第2位為6：1個(gè)（即167）。共5+4+…+1=15個(gè)。
所以，滿足要求的r共有36個(gè)。

只有1行，為兩個(gè)正整數(shù)，用一個(gè)空格隔開：
k w

1行，是一個(gè)正整數(shù)，為所求的計(jì)算結(jié)果，即滿足條件的不同的r的個(gè)數(shù)（用十進(jìn)制數(shù)表示），要求最高位不得為0，各數(shù)字之間不得插入數(shù)字以外的其他字符（例如空格、換行符、逗號(hào)等）。
（提示：作為結(jié)果的正整數(shù)可能很大，但不會(huì)超過200位）

3  7

36