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.
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).
First line of output file must contain only one number - quantity of peaceful positions.
Test #1 8 2 6 8 1
Test #2 8 8 3 4 1
Test #1 68
Test #2 108
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov