C0990 [HNOI2006]花仙子的魔法

内存限制:256 MB 时间限制:1000 ms

题目描述

相传,在天地初成的远古时代,世界上只有一种叫做 “元” 的花。接下来,出 现了一位拥有魔法的花仙子,她能给花附加属性,从此,“元”便不断变异,产生了大千世界千奇百怪的各种各样的花。据说,花仙子既可存在于二维空间(平面),又可存在于三维空间(立体),还可存在于 $n$ 维空间(想象)。二维空间的点可用向量($x_1,x_2$)表示,三维空间的点可用向量($x_1,x_2,x_3$)表 示,一般来说,$n$ 维空间的点可用向量($x_1,x_2,…,x_n$)表示。而 $n$ 维空间中两点($x_1,x_2,…,x_n$)与($w_1,w_2,…,w_n$)之间的距离定义为 $\sqrt{\sum_{i=1}^n(X_i-W_i)^2}$。

在 $n$ 维空间中,花仙子每实施魔法就要选择一个参考点($w_1,w_2,…,w_n$)和一个作用半径 $r$,并且参考点的位置和作用半径的大小可以任意选择。这时,$n$ 维空间中所有与参考点($w_1,w_2,…,w_n$)之间的距离小于作用半径r的花都会受到这次魔法的影响。每次魔法都会给受到影响的花带来不同的属性,且的效果可以叠加。一般来说,若花仙子总共实施了 $m$ 次魔法,则 $n$ 维空间中处于某点的花所具有的属性可用长度为 $m$ 的二进制串 $a_1a_2…a_m$ 来描述,其中对 $1≤i≤m$,若该花受到第 $i$ 次魔法的影响,则 $a_i$ 的值为 $1$,否则为 $0$。显然,不同的属性对应不同的花。 现在的问题是:花仙子在 $n$ 维空间中实施了 $m$ 次魔法后,最多能得到多少种不同的花?

输入格式

包含两个整数,并用一个空格隔开,第一个整数表示实施魔法的次数 $m$,第二个整数表示空间的维数 $n$。

其中,$1≤m≤100,1≤n≤15$。

输出

仅包含一个整数,表示花仙子在 $n$ 维空间中实施了 $m$ 次魔法后,最多能得到多少种不同的花。

样例

样例输入 1

3 1

样例输出 1

6

提示