描述

歷經(jīng)千辛萬苦，小Hi和小Ho終于到達(dá)了舉辦美食節(jié)的城市！雖然人山人海，但小Hi和小Ho仍然抑制不住興奮之情，他們放下行李便投入到了美食節(jié)的活動(dòng)當(dāng)中。美食節(jié)的各個(gè)攤位上各自有著非常多的有意思的小游戲，其中一個(gè)便是這樣子的：

小Hi和小Ho領(lǐng)到了一個(gè)大小為N*M的長方形盤子，他們可以用這個(gè)盒子來裝一些大小為2*1的蛋糕。但是根據(jù)要求，他們一定要將這個(gè)盤子裝的滿滿的，一點(diǎn)縫隙也不能留下來，才能夠?qū)⑦@些蛋糕帶走。

這么簡單的問題自然難不倒小Hi和小Ho，于是他們很快的就拿著蛋糕離開了~

但小Ho卻不只滿足于此，于是他提出了一個(gè)問題——他們有多少種方案來裝滿這個(gè)N*M的盤子呢？

值得注意的是，這個(gè)長方形盤子的上下左右是有區(qū)別的，如在N=4, M=3的時(shí)候，下面的兩種方案被視為不同的兩種方案哦！

輸入

每個(gè)測試點(diǎn)（輸入文件）有且僅有一組測試數(shù)據(jù)。

每組測試數(shù)據(jù)的第一行為兩個(gè)正整數(shù)N、M，表示小Hi和小Ho拿到的盤子的大小。

對于100%的數(shù)據(jù)，滿足2<=N<=1000, 3<=m<=5。<>

輸出

考慮到總的方案數(shù)可能非常大，只需要輸出方案數(shù)除以1000000007的余數(shù)。

2 4樣例輸出           5
#include<iostream>#include<cstring>#include<algorithm>#define MOD 1000000007using namespace std;int d[1 << 10], n, m;int dp(){	int ans = 0, i, j, k, temp = 1 <<2*m, full = (1 << m) - 1 ;	d[0] = 1;	for (i = 1;i <= n;i++)	{		for (k = 0;k <m;k++)			for (j = 0;j <temp;j++)			{				int number = 0, t = j;				while (t)				{					if ((t & 1) == 0)						break;					t = t / 2;					number++;				}				if (number < k + 1) continue;				if (j&(1 << (k + m)))				{					d[j]=(d[j] + d[(j&~(1 << (m + k)))&~(1 << k)])%MOD;				}//第K位為空，豎放				else if (j&(1 << (k + 1)) && k < m - 1)				{					d[j]=(d[j] + d[j&~(1 << (1 + k))&~(1 << k)])%MOD;				}//第K位為空，橫放			}		for (j = 0;j < 1<<m;j++)			d[j] = d[(j<<m)| full];		for (j = 1 << m;j < temp;j++)			d[j] = 0;	}	return d[0];}int main(){	cin >> n >> m;	cout << dp();	return 0;}