当前没有测试数据。

题目描述

有一块土地，可以看成是一个 N×M 的网格图。

现在要在这块土地上种植 $K$ 棵树。树必须种植在格子中。同一行最多只能种植一棵树，同一列最多也只能种植一棵树。

但是土地右上角 P×Q 的网格部分由于土质原因，不能种树。

例如，当 $N, M, P, Q$ 依次为 $4, 5, 2, 3$ 时，对应土地的网格图如下所示，灰色区域不能种树。

问：有多少种不同的种植方案？答案可能很大，你只需要输出其 mod 998244353 的值。

注：两种种植方案不同，当且仅当至少存在一个格子，在一种方案中种植了树，而在另一种方案中没有种植树。

输入格式

一行，包含五个整数，分别代表 $N, M, P, Q, K$。

输出格式

一行，一个整数，表示答案 mod 998244353

样例1输入

2 4 1 2 2

样例1输出

6

样例2输入

1234 567 88 99 100

样例2输出

108896566

数据规模

• 部分数据，满足 $P=0$；
• 部分数据，满足 $N, M ≤ 8；P,Q ≤ 4$。
• $100\%$ 的数据，满足 $N, M ≤ 2000；P,Q ≤ 1000；P<N；Q<M；0 ≤ K ≤ 1000$，且至少有一种种植方案。