#P18096. Rook

Rook

Rook

题目描述

在一个 N×MN\times M 的棋盘上放置 KK 个彼此不同的车。要求每个格子至多放一个车,而且每一行、每一列都至少有一个车。

求合法放置方案数,对 998244353998244353 取模。车彼此有区别,因此交换两辆车所在的位置会产生不同方案。本题不要求车互不攻击。

输入格式

一行三个整数 N,M,KN,M,K。

输出格式

一行一个整数,表示方案数的模值。

数据范围

1≤N,M,K≤1051\le N,M,K\le10^5。不额外保证存在合法放置方案。

样例 1

输入

2 2 3

输出

24

样例 2

输入

5 3 4

输出

0

样例 3

输入

353 442 899

输出

623104742