题目描述

风靡全球的游戏《原鱼》中有一个副本叫做“深境方块”，每半个月刷新一次，完成挑战可以获得大量奖励。

具体来说，副本中有一个长方体状的迷宫，从上到下一共有 $3$ 层，可以将其分别称为上层、中层和下层，每一层都有 $n \times m$ 个房间，呈网格状分布。上层的每个房间与其四周存在的房间都是相通的，并且可以通往中层的相邻房间；中层的房间如同过道，只能通往下层的相邻房间；下层的每个房间与其四周存在的房间也都是相通的。

开启挑战后玩家可以任选一间上层房间作为起点，然后按照上述规则移动，并在通过 $k$ 个不同的房间后完成挑战，所有房间都可以多次重复进入。

显然，每个房间中都有怪物需要清理，但胖头鱼是游戏策划，角色和装备应有尽有，所以不用担心难度问题。但是为了评估副本的多样性，他想知道有多少种不同的挑战方法，作为临时工的你应该已经具备基本的自觉了吧。

两种挑战方法被认为是不同的，当且仅当它们通过的房间集合是不同的，即存在某个房间，恰好有一种挑战方法通过了该房间。

输入格式

只有一行，包含三个整数 $n$ 、 $m$ 和 $k$ ，表示每层迷宫有 $n \times m$ 个房间，需要通过 $k$ 个不同的房间。

输出格式

只有一个整数，表示有多少种不同的挑战方法。

数据样例

【样例 1 输入】

存放在 sample/cube 目录下的 cube1.in 文件中。

2 3 3

【样例 1 输出】

存放在 sample/cube 目录下的 cube1.out 文件中。

30

【样例 1 解释】

当所有通过房间都在上层时，所有房间一排有 $2$ 种方案，呈拐角状有 $4 \times 2 = 8$ 种方案，共 $10$ 种方案。

当上层通过了 $2$ 个房间且中层通过了 $1$ 个房间时，上层房间有 $7$ 种方案，每种方案都可以从 $2$ 个相邻中层房间中选一个，所以有 $7 \times 2 = 14$ 种方案。

当三层各通过了 $1$ 个房间时，共有 $6$ 种方案。

因此总共有 $10 + 14 + 6 = 30$ 种方案。

【样例 2 输入】

存放在 sample/cube 目录下的 cube2.in 文件中。

1 4 5

【样例 2 输出】

存放在 sample/cube 目录下的 cube2.out 文件中。

26

【样例 2 解释】

当上层通过了 $4$ 个房间时，只有 $1$ 种方案，且中层可以任选一个房间通过，共 $4$ 种方案。

当上层通过了 $3$ 个房间时，有 $2$ 种对称方案，每种方案可以任选一对中层和下层相邻的房间，共 $2 \times 3 = 6$ 种方案。

当上层通过了 $2$ 个房间时，如果靠边，根据中层房间的选择，共有 $2 \times (1 + 2) = 6$ 种方案；如果居中，则有 $2 \times 2 = 4$ 种方案，共 $10$ 种方案。

当上层通过了 $1$ 个房间时，中层也只能通过对应的相邻房间，根据位置下层房间共有 $1 + 2 + 2 + 1 = 6$ 种方案。

因此总共有 $4 + 6 + 10 + 8 = 26$ 种方案。

【样例 3 和 4】

存放在 sample/cube 目录下的 cube3.in 和 cube3.out 、 cube4.in 和 cube4.out 文件中。 cube.zip

数据说明

对于所有测试点，满足 $1 ≤ n \times m ≤ 400$ 、 $1 ≤ k ≤ 10$ 。

子任务及其特殊属性如下：

• 子任务 $1$ 占 $20\%$ 的分数，满足 $n = 1$ ，表示每层房间都是一排。
• 子任务 $2$ 占 $30\%$ 的分数，满足 $k ≤ 5$ ，表示需要通过的房间数较少。
• 子任务 $3$ 占 $30\%$ 的分数，满足 $n \times m ≤ 20$ ，表示房间的总数较少。
• 子任务 $4$ 占 $20\%$ 的分数，没有特殊属性。