Problem Description

A factory produces colored cubes. During manufacturing, a cuboid wooden block is taken as the blank, with size $a \times b \times c$. Usually, it is first cut into $a \cdot b \cdot c$ unit cubes, and then all faces of each cube are painted.

However, due to an error in the machine tool program written using the "Coder 239" Vibe Coding system, this time everything was reversed: first, all outer surfaces of the whole cuboid were painted, and then it was cut into unit cubes. Therefore, in this batch of products, different cubes may have different numbers of painted faces.

To assess the loss, you need to compute 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 cuboid, and the number $k$ ($0 \le k \le 6$) — the number of painted faces of a cube.

Output Format

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

3 3 3 3

8

4 2 1 3

4

Hint

Scoring Rules.

This problem has 20 test points. Each test point is scored independently and is worth 5 points.

During the contest, you will learn the judging result for each test point.

Translated by DeepSeek.

Translated by ChatGPT 5