<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

241. The United Fields of Chessboardia
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



Little boy Vasya likes to play chess very much. Every Wednesday and Saturday at four o'clock after midday he goes to "An Check-Mate" (ACM) chess Club for five hours. Here Vasya solves many interesting chess problems and tasks.
Vasya has a great skill of that. He proves this skill everyday. Now, he can solve any simple chess problem faster than any his classmate. But he doesn't know how to solve difficult chess problems, and wants to find out a way to learn that. His trainer said, that the only way to learn how to solve difficult problem - is to know how others do that. And Vasya has thought up a problem for solving by some clever man. Please solve it and help Vasya to make an self-improvement.
Trying to create a really difficult problem Vasya decided not to use standard 8x8 chessboard.
Consider two chessboards NxN and MxM aligned to integer grid such that the left-bottom corner of the second chessboard located not to the bottom and not to the left from the left-bottom corner of the first chessboard. Let us call horizontal distance the number of columns located between two corners. Analogically, we will define the vertical distance (look at figure for clearance). Your task is, given sizes of chessboards, horizontal and vertical distances between their left-bottom corners and number K, to calculate a number of ways to place K rooks in peaceful position on union of these two boards. Position is called peaceful, if any two rooks don't attack each other. Rooks attack each other if located at same vertical or horizontal.


Input
On first line of input file, there are sizes of chessboards, N and M respectively (0<=N,M<=20), horizontal and vertical distances between left-bottom corners of chessboards, W and H (0<=W,H<=10^9) and K - number of rooks (0<=K<=10^9).

Output
First line of output file must contain only one number - quantity of peaceful positions.

Sample test(s)

Input
Test #1
8 2 6 8 1

Test #2
8 8 3 4 1

Output
Test #1
68

Test #2
108
Author:	Alexey Preobrajensky
Resource:	---
Date:	October, 2003

<|response|>
## 1. Abridged problem statement

We have two chessboards placed on the same infinite integer grid:

- first board: `N × N`, bottom-left corner at `(0, 0)`;
- second board: `M × M`, bottom-left corner at `(W, H)`.

Consider all cells belonging to the union of these two boards.

Count the number of ways to place exactly `K` rooks on these cells so that no two rooks share the same row or column.

Constraints:

```text
0 ≤ N, M ≤ 20
0 ≤ W, H ≤ 10^9
0 ≤ K ≤ 10^9
```

The answer can be very large, so it must be printed exactly.

---

## 2. Key observations needed to solve the problem

### Observation 1: Only occupied rows and columns matter

Although `W` and `H` can be huge, each board has size at most `20`.

The first board uses columns:

```text
[0, N)
```

The second board uses columns:

```text
[W, W + M)
```

So the total number of relevant columns is at most:

```text
N + M ≤ 40
```

The same is true for rows.

Large empty gaps between the boards are irrelevant.

---

### Observation 2: Split columns and rows into three types

Columns can be divided into:

1. columns belonging only to the first board;
2. columns shared by both boards;
3. columns belonging only to the second board.

Rows can be divided in the same way.

Let:

```text
c1 = number of first-only columns
cs = number of shared columns
c2 = number of second-only columns
```

and:

```text
r1 = number of first-only rows
rs = number of shared rows
r2 = number of second-only rows
```

The number of shared columns is the length of the intersection:

```text
[0, N) ∩ [W, W + M)
```

Similarly, the number of shared rows is:

```text
[0, N) ∩ [H, H + M)
```

---

### Observation 3: Allowed row types depend on column type

A first-only column contains cells only from the first board, so it can use:

- first-only rows;
- shared rows.

A second-only column contains cells only from the second board, so it can use:

- shared rows;
- second-only rows.

A shared column belongs to both boards, so it can use:

- first-only rows;
- shared rows;
- second-only rows.

So the allowed combinations are:

| Column type | first-only rows | shared rows | second-only rows |
|---|---:|---:|---:|
| first-only column | yes | yes | no |
| shared column | yes | yes | yes |
| second-only column | no | yes | yes |

---

### Observation 4: This is a rook placement / matching counting problem

A peaceful rook placement means:

- at most one rook in each chosen column;
- at most one rook in each chosen row.

We can process columns one by one.

For each column, either:

1. place no rook in it;
2. place one rook in an allowed unused row.

---

## 3. Full solution approach based on the observations

### Step 1: Compute overlaps

Define a helper function:

```text
overlap([0, A), [B, B + C))
```

It returns:

```text
max(0, min(A, B + C) - max(0, B))
```

For columns:

```text
cs = overlap([0, N), [W, W + M))
c1 = N - cs
c2 = M - cs
```

For rows:

```text
rs = overlap([0, N), [H, H + M))
r1 = N - rs
r2 = M - rs
```

---

### Step 2: Dynamic programming state

Use:

```text
dp[a][b][c]
```

where:

- `a` = number of unused first-only rows;
- `b` = number of unused shared rows;
- `c` = number of unused second-only rows.

Initially all rows are unused:

```text
dp[r1][rs][r2] = 1
```

---

### Step 3: Process columns

For every column, depending on its type, we know which row types it can use.

From state `dp[a][b][c]`, we can:

#### Skip this column

```text
next[a][b][c] += dp[a][b][c]
```

#### Place rook in a first-only row

Possible only if this column allows first-only rows and `a > 0`.

There are `a` choices for the actual row:

```text
next[a - 1][b][c] += dp[a][b][c] * a
```

#### Place rook in a shared row

Possible only if allowed and `b > 0`:

```text
next[a][b - 1][c] += dp[a][b][c] * b
```

#### Place rook in a second-only row

Possible only if allowed and `c > 0`:

```text
next[a][b][c - 1] += dp[a][b][c] * c
```

Process:

```text
c1 first-only columns
cs shared columns
c2 second-only columns
```

---

### Step 4: Extract the answer

At the end, the number of placed rooks is equal to the number of used rows:

```text
(r1 - a) + (rs - b) + (r2 - c)
```

Sum all states where this value equals `K`.

If `K` is too large, no state will match and the answer is `0`.

---

### Complexity

The number of states is at most:

```text
21 × 21 × 21
```

The number of processed columns is at most:

```text
40
```

So the algorithm is easily fast enough.

The answer can be huge, so we need arbitrary-precision integers.

---

## 4. C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    long long W, H, K;

    cin >> N >> M >> W >> H >> K;

    /*
        Computes the length of intersection of intervals:

            [0, lenA)
            [startB, startB + lenB)

        In this problem:
        - first board always starts at coordinate 0;
        - second board starts at W or H.
    */
    auto overlap = [](long long startB, long long lenB, long long lenA) -> int {
        long long left = max(0LL, startB);
        long long right = min(lenA, startB + lenB);
        return (int)max(0LL, right - left);
    };

    // Column type counts.
    int sharedCols = overlap(W, M, N);
    int firstOnlyCols = N - sharedCols;
    int secondOnlyCols = M - sharedCols;

    // Row type counts.
    int sharedRows = overlap(H, M, N);
    int firstOnlyRows = N - sharedRows;
    int secondOnlyRows = M - sharedRows;

    /*
        dp[a][b][c] = number of ways after processing some columns, where:

        a = unused first-only rows
        b = unused shared rows
        c = unused second-only rows
    */
    vector<vector<vector<cpp_int>>> dp(
        firstOnlyRows + 1,
        vector<vector<cpp_int>>(
            sharedRows + 1,
            vector<cpp_int>(secondOnlyRows + 1)
        )
    );

    // Initially, all rows are unused.
    dp[firstOnlyRows][sharedRows][secondOnlyRows] = 1;

    /*
        Process one column.

        canFirst  = can place a rook in a first-only row
        canShared = can place a rook in a shared row
        canSecond = can place a rook in a second-only row
    */
    auto processColumn = [&](bool canFirst, bool canShared, bool canSecond) {
        vector<vector<vector<cpp_int>>> nextDp(
            firstOnlyRows + 1,
            vector<vector<cpp_int>>(
                sharedRows + 1,
                vector<cpp_int>(secondOnlyRows + 1)
            )
        );

        for (int a = 0; a <= firstOnlyRows; a++) {
            for (int b = 0; b <= sharedRows; b++) {
                for (int c = 0; c <= secondOnlyRows; c++) {
                    cpp_int cur = dp[a][b][c];

                    if (cur == 0) {
                        continue;
                    }

                    // Option 1: do not place a rook in this column.
                    nextDp[a][b][c] += cur;

                    // Option 2: place a rook in one of the unused first-only rows.
                    if (canFirst && a > 0) {
                        nextDp[a - 1][b][c] += cur * a;
                    }

                    // Option 3: place a rook in one of the unused shared rows.
                    if (canShared && b > 0) {
                        nextDp[a][b - 1][c] += cur * b;
                    }

                    // Option 4: place a rook in one of the unused second-only rows.
                    if (canSecond && c > 0) {
                        nextDp[a][b][c - 1] += cur * c;
                    }
                }
            }
        }

        dp = move(nextDp);
    };

    /*
        Process columns by type.

        First-only columns can use:
        - first-only rows
        - shared rows
    */
    for (int i = 0; i < firstOnlyCols; i++) {
        processColumn(true, true, false);
    }

    /*
        Shared columns can use all row types.
    */
    for (int i = 0; i < sharedCols; i++) {
        processColumn(true, true, true);
    }

    /*
        Second-only columns can use:
        - shared rows
        - second-only rows
    */
    for (int i = 0; i < secondOnlyCols; i++) {
        processColumn(false, true, true);
    }

    cpp_int answer = 0;

    /*
        Count states where exactly K rows have been used.
        Since each rook uses exactly one row, this is also the number of rooks.
    */
    for (int a = 0; a <= firstOnlyRows; a++) {
        for (int b = 0; b <= sharedRows; b++) {
            for (int c = 0; c <= secondOnlyRows; c++) {
                long long placed =
                    (firstOnlyRows - a) +
                    (sharedRows - b) +
                    (secondOnlyRows - c);

                if (placed == K) {
                    answer += dp[a][b][c];
                }
            }
        }
    }

    cout << answer << '\n';

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
# Read input.
# N, M = sizes of the two boards.
# W, H = horizontal and vertical shift of the second board.
# K = number of rooks to place.
N, M, W, H, K = map(int, input().split())


def overlap(start_b, len_b, len_a):
    """
    Return the length of intersection of intervals:

        [0, len_a)
        [start_b, start_b + len_b)

    The first board starts at 0.
    The second board starts at start_b.
    """

    left = max(0, start_b)
    right = min(len_a, start_b + len_b)

    return max(0, right - left)


# Count column types.
shared_cols = overlap(W, M, N)
first_only_cols = N - shared_cols
second_only_cols = M - shared_cols

# Count row types.
shared_rows = overlap(H, M, N)
first_only_rows = N - shared_rows
second_only_rows = M - shared_rows

"""
dp[a][b][c] = number of ways after processing some columns, where:

a = number of unused first-only rows
b = number of unused shared rows
c = number of unused second-only rows
"""
dp = [
    [
        [0 for _ in range(second_only_rows + 1)]
        for _ in range(shared_rows + 1)
    ]
    for _ in range(first_only_rows + 1)
]

# Initially, every row is unused.
dp[first_only_rows][shared_rows][second_only_rows] = 1


def process_column(can_first, can_shared, can_second):
    """
    Process one column.

    can_first:
        whether this column can use first-only rows

    can_shared:
        whether this column can use shared rows

    can_second:
        whether this column can use second-only rows
    """

    global dp

    next_dp = [
        [
            [0 for _ in range(second_only_rows + 1)]
            for _ in range(shared_rows + 1)
        ]
        for _ in range(first_only_rows + 1)
    ]

    for a in range(first_only_rows + 1):
        for b in range(shared_rows + 1):
            for c in range(second_only_rows + 1):
                cur = dp[a][b][c]

                if cur == 0:
                    continue

                # Option 1: place no rook in this column.
                next_dp[a][b][c] += cur

                # Option 2: place a rook in a first-only row.
                if can_first and a > 0:
                    # There are a choices for the actual row.
                    next_dp[a - 1][b][c] += cur * a

                # Option 3: place a rook in a shared row.
                if can_shared and b > 0:
                    # There are b choices for the actual row.
                    next_dp[a][b - 1][c] += cur * b

                # Option 4: place a rook in a second-only row.
                if can_second and c > 0:
                    # There are c choices for the actual row.
                    next_dp[a][b][c - 1] += cur * c

    dp = next_dp


# First-only columns can use first-only and shared rows.
for _ in range(first_only_cols):
    process_column(True, True, False)

# Shared columns can use all row types.
for _ in range(shared_cols):
    process_column(True, True, True)

# Second-only columns can use shared and second-only rows.
for _ in range(second_only_cols):
    process_column(False, True, True)


answer = 0

# Sum all final states where exactly K rooks were placed.
for a in range(first_only_rows + 1):
    for b in range(shared_rows + 1):
        for c in range(second_only_rows + 1):
            placed = (
                (first_only_rows - a)
                + (shared_rows - b)
                + (second_only_rows - c)
            )

            if placed == K:
                answer += dp[a][b][c]

print(answer)
```