No.2527 H and W
タグ : / 解いたユーザー数 132
作問者 :
srjywrdnprkt
/ テスター :
👑 Problem Statement
There is a grid of cells with $H$ rows and $W$ columns. Initially, all cells are black.
Consider performing the following operation.
- Choose some rows (possibly $0$ rows) and some columns (possibly $0$ columns). Then, paint red all cells contained in the chosen rows and all cells contained in the chosen columns.
Here, two ways of choosing are considered different if there is a row or a column that is chosen in only one of them.
Input
$H\ W\ K$
All inputs are integers and satisfy the following constraints.
- $1\leq H, W \leq 10^6$
- $1\leq K \leq HW$
Output
Output the number of ways to choose rows and columns satisfying the condition, modulo $998244353$.
Print a newline at the end.
Sample
Sample 1
Input
2 3 2
Output
9
The following $9$ ways satisfy the condition.
- Column $1$, column $2$
- Column $1$, column $3$
- Column $2$, column $3$
- Row $1$, column $1$
- Row $1$, column $2$
- Row $1$, column $3$
- Row $2$, column $1$
- Row $2$, column $2$
- Row $2$, column $3$
Sample 2
Input
5 5 7
Output
0
There may be no way of choosing that satisfies the condition.
Sample 3
Input
1000000 1000000 1000000
Output
894293636
Output the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。