Given a chessboard with a missing corner, the dimensions are specified as follows:
For example, with $a = b = c = d = 2$:
Count the number of ways to place $k$ rooks on the chessboard such that no two rooks can attack each other. In other words, no two rooks should be in the same row or column.
### Input
- A single line containing five integers $a, b, c, d, k$.
### Output
- Print an integer representing the number of valid placements modulo $10^5+3$.
### Constraints
- $1 \le a,b,c,d,k \le 1000$.
### Example
Input:
```
2 2 2 2 2
```
Output:
```
38
```
