1858: 涂墙游戏

Admin在冬令营比赛的最后一小时没事做，于是便有了本游戏。这个游戏有一个N*M的墙面，我们的目标就是将整个墙面铺满。涂墙的方法有两种，一种是可以每次涂长度为1单位的墙面，第二种是每次可以涂3单位的墙面，且有a1种不同的涂料可以选择。

   对于第二种涂得方法，我们有一些限制，通常情况下我们可以竖着连续涂三个单位长度（注意，必须涂满竖着涂满三个）。特殊的，我们可以在第i列和第i+1列（I∈奇数）底部或第i列和第i+1列（I∈偶数）顶部涂一条为"L"形状的。具体参见如下图

在第i列和第i+1列（I∈奇数）中绿色的样子

在第i列和第i+1列（I∈偶数）中蓝色的样子

求总共涂色的方案数（涂料不同、位置不同、方法不同都将认为是不同的方案）

共一行 三个正整数n,m,a1，分别表示行数、列数，a1含义上文已经描述。

共一行，输出方案数mod 19931012的值

3 2 1

6