车的放置(Placing Rooks)

有下面这样的一个网格棋盘， $a,b,c,d$ 表示了对应边长度，也就是对应格子数：

当 $a=b=c=d=2$ 时，对应下面这样一个棋盘：

要在这个棋盘上放 $k$ 个相互不攻击的车，也就是这 $k$ 个车没有两个车在同一行，也没有两个车在同一列，问有多少种方案。

只有一行，为五个非负整数，分别代表 $a,b,c,d$ 和 $k$ 。

输出一行一个整数代表答案 $\bmod$ $10^5+3$ 后的结果。

2 2 2 2 2

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1350。

Subtask	分值	测试点编号	说明
0	10	1~2	样例及最小边界测试
1	20	3~8	$0 \le a, b, c, d, k \le 4$
2	15	9~11	Hack 数据： $b = 0$ （退化为单个矩形）、 $k = 0$ （答案 $1$ ）、 $a = c = 0$ 或极限 $k$
3	30	12~20	$0 \le a, b, c, d, k \le 300$
4	25	21~25	$0 \le a, b, c, d, k \le 1000$ 组合计数满规模测试

出处：原题链接

#P1350. 车的放置(Placing Rooks)