At a factory, colored cubes are manufactured. For this, a blank is taken — a wooden bar of size $a \times b \times c$. First, it is sawn into $a \cdot b \cdot c$ unit cubes, and then each cube is painted on all sides.

However, due to an error in the machine program written using the vibe-coding system “Coder 239”, this time everything happened in reverse: first, the sides of the bar were painted on all sides, and then it was sawn into unit cubes. Because of this, different cubes in this batch could end up with a different number of painted faces.

To assess the damage, it is necessary to count the number of cubes that have exactly $k$ painted faces.

Input Format

The only line contains four numbers: $a$, $b$, $c$ $(1 \le a, b, c \le 10^5)$ — the dimensions of the bar, and the number of painted faces of a cube $k$ $(0 \le k \le 6)$.

Output Format

Output one number — the number of unit cubes with the given number of painted faces.

Scoring

This problem has 20 tests, each evaluated independently for 5 points.
During the contest, you are informed of the checking result for each test.

Example

Input

3 3 3 3

Output

8

Input

4 2 1 3

Output

4