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

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

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

输入一行五个非负整数 a, b, c, d, k;
（0 <= a, b, c, d, k <= 1000且至少有一种可行的方案）

输出一行一个整数表示答案对100003取模后的结果。