3060 - 管道布局
时间限制 : 2 秒
内存限制 : 128 MB
该市正在部分城区建设集中供暖系统。市区占地面积是一个矩形区域,由排列成网格的方形块组成。集中供暖系统是将用于通过该地区每个街区输送热水的一个封闭的管道回路。市议会正在考虑每个地区管道的不同布局。
为了尽量减少管道的总长度,但仍然为该地区的每个街区提供热水,每个街区必须有一根管道。每个街区的管道必须连接到两个相邻街区的管道。所以,最多有六个每个区块中可能的管道配置:
为了计划他们的规划活动,市议会想知道给定城区的管道布局的方案数。例如,16个区块排列成4乘4的网格:
输入
仅两个整数,表示城区的矩形的行数r和列数c。保证r > 1,c > 1 ,r×c \leq 100
输出
仅一个数字,表示方案数
样例
输入
4 4
输出
6
输入
2 8
输出
1
输入
12 8
输出
102283239429
来源
codeforces