最后两个点暴力超时怎么改
xxz非常喜欢玩这样一个游戏:他将要在n*m的棋盘上进行染色,并且满足以下个要求:
1:每个格子必须染上颜色,且只能染上黑白两种颜色
2:对于任何一个2x2的正方形,黑色格子的个数必须为奇数
xxz很想知道他有多少种可能的染色方案。xxz发觉这个数会很大,所以他只想知道所有的方案数对10^9+7取模的结果。
输入格式
一行两个数n,m,代表棋盘的长为n,宽为m。
输出格式
一行,代表总方案数对10^9+7取模的结果
输入输出样例
输入 #1复制
2 2
输出 #1复制
8
说明/提示
对于30%的数据:n<=5,m<=5
对于60%的数据:n<=10,m<=10
对于80%的数据:n<=10^6,m<=10^6
对于100%的数据:n<=10^10,m<=10^10