0238. The United Fields of Chessboardia

Input file name:	chessbrd.in
Output file name:	chessbrd.out
Time limit:	250 ms
Memory limit:	64 megabytes

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.

Input file

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⁹) and K – number of rooks (0 ≤ K ≤ 10⁹).

Output file

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

Examples:

chessbrd.in	chessbrd.out
8 2 6 8 1	68
8 8 3 4 1	108

Source: Petrozavodsk Winter 2004. SPb ETU Contest, Sunday, February 01

Discuss       Submit a solution



Printable version