迷失的国王

题目描述

在一个 $n \times m$ 的棋盘形宫殿中，国王想要放置两个相同的宝藏。已知这两个宝藏之间的 曼哈顿距离 恰好为 $k$，现在需要统计共有多少种放置方式。

平面上两点 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的曼哈顿距离定义为：

请你输出在一个 $n \times m$ 的棋盘中，放置两个宝藏且它们曼哈顿距离恰好为 $k$ 的方案数。

输入格式

从标准输入按以下格式读取数据：

$n$ $m$ $k$

其中：

• 输入三个正整数 $n,m,k$。

输出格式

输出一个整数，表示满足条件的方案数。

数据范围

• $1 \le n,m,k \le 10^6$

对于部分数据：

• $20\%$ 的数据满足：$1 \le n,m,k \le 100$
• $40\%$ 的数据满足：$1 \le n,m,k \le 500$
• $60\%$ 的数据满足：$1 \le n,m,k \le 5000$
• $100\%$ 的数据满足：$1 \le n,m,k \le 10^6$

样例

8 8 14

2

8 8 3

248

4 3 3

17