车的放置

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

棋盘上方 $b$ 行各有 $a$ 列，下方 $d$ 行各有 $a+c$ 列。请放置 $k$ 个任意两车不同行、不同列的车，求方案数模 $100003$。

输入格式

一行五个非负整数 $a,b,c,d,k$。

输出格式

输出一个整数。

样例输入 1

2 2 2 2 2

样例输出 1

38

数据范围

对所有数据，$0\le a,b,c,d,k\le1000$，且至少存在一种可行方案。