陇西行四首·其二

作者：陈陶

誓扫匈奴不顾身
五千貂锦丧胡尘
可怜无定河边骨
犹是春闺梦里人

晚唐时期，m名匈奴间谍混入了唐军阵营和原本的唐军组成了一个总共ab个人的方阵，只要有两个匈奴相邻（即一个匈奴在另一个匈奴的前后左右中的一个方位）就会爆发混乱。请问现在唐军将领有多少种布阵方法使其不发生混乱。
第一行三个整数m，a，b，表示匈奴间谍数和方阵的长宽
一个整数，表示合法布阵的个数

输入样例

2 3 2

输出样例

8

样例解释

假设0表示唐军，1表示匈奴间谍，则合法的情况如下

第一种

100
010

第二种

100
001

第三种

101
000

第四种

001
010

第五种

001
100

第六种

010
001

第七种

010
100

第八种

000
101

数据范围

对于100%的数据，1≤a≤80，1≤b≤80，1≤a*b≤80，0≤m≤20，并且m≤a*b
ps：这道题目的空间限制为65536KB