P1350 Placing Rooks

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.

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

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

#### 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