Description

There is a grid chessboard as shown below, where $a, b, c, d$ represent the lengths of the corresponding edges, i.e., the number of grid cells.

When $a = b = c = d = 2$, the chessboard looks like this:

We need to place $k$ rooks on this chessboard such that no two rooks attack each other, meaning no two rooks are in the same row or the same column. The task is to determine the number of possible arrangements. The answer should be output modulo $10^5 + 3$.

Input Format

The first line contains five non-negative integers $a, b, c, d,$ and $k$.

Output Format

Output a single positive integer, which is the answer modulo $10^5 + 3$.

Sample 1

2 2 2 2 2

38

Data Range and Hints

For all data, $1 \le a, b, c, d, k \le 1000$, and it is guaranteed that there is at least one feasible arrangement.