#P6511. Domino Colorings

    ID: 5111 传统题 1250ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-轮廓线 DP子集构造DP 套 DP状压 DP计数 DP哈希表滚动数组

Domino Colorings

题目描述

n×mn\times m 的网格,用 1×21\times 2 的骨牌(恰好1黑1白)。问能够铺出的不同颜色的网格方案数,答案对 109+710^9+7 取模。

注意不同铺法但是颜色相同算一种。

输入格式

一行两个正整数表示 n,mn,m。

输出格式

一个非负整数,表示你的答案。

样例

2 3
16
4 4
2798
6 300
472442515

数据范围

n≤6,m≤300n\le 6,m\le 300