Non‐Attacking Rooks on a Rectangular Board

Given a board defined by four positive integers \(a, b, c, d\) which represent the number of cells along its corresponding edges, the board is constructed as a rectangle with \(a+d\) columns and \(b+c\) rows. For example, when \(a = b = c = d = 2\), the board becomes a \(4 \times 4\) grid.

Your task is to place \(k\) rooks on the board so that no two rooks attack each other, i.e. no two rooks share the same row or the same column. Compute the total number of valid arrangements.

The answer can be computed by first choosing \(k\) distinct rows from the total \(b+c\) rows and \(k\) distinct columns from the total \(a+d\) columns, and then arranging the \(k\) rooks in these chosen rows and columns (each arrangement corresponds to a permutation of \(k\) elements). Thus, the total number of arrangements is:

[ \binom{b+c}{k} \times \binom{a+d}{k} \times k! ]

inputFormat

The input consists of a single line containing five space-separated integers: \(a, b, c, d, k\), where \(a, b, c, d\) are the side lengths (in cells) of the board and \(k\) is the number of rooks to place.

You may assume that all integers are positive and that \(k \leq \min(a+d, b+c)\).

outputFormat

Output a single integer: the number of ways to place the \(k\) rooks on the board such that no two rooks are in the same row or the same column.

sample

2 2 2 2 2

72