Description

There is a grid board as shown below, where $a,b,c,d$ denote the lengths of the corresponding sides, i.e., the numbers of cells on those sides:

When $a=b=c=d=2$, the corresponding board is as follows:

You need to place $k$ non-attacking rooks on this board, meaning that among these $k$ rooks, no two share the same row and no two share the same column. Find the number of such placements.

Input Format

A single line with five non-negative integers, representing $a,b,c,d$ and $k$.

Output Format

Output one line with a single integer, which is the answer $\bmod$ $10^5+3$.

2 2 2 2 2

38

Hint

Constraints and Notes

• For some testdata, it is guaranteed that $b=0$.
• For some testdata, it is guaranteed that $a,b,c,d\leq 4$.
• For $100\%$ of the data, it is guaranteed that $0\leq a,b,c,d,k\leq 10^3$, and there is at least one feasible solution.

Translated by ChatGPT 5