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 CheckMate" (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 selfimprovement.
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 leftbottom corner of the second chessboard located not to the bottom and not to the left from the leftbottom 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 leftbottom 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 leftbottom 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

Server time: 20180619 10:28:15  Online Contester Team © 2002  2016. All rights reserved. 

