Tiberiu Danet

Borg

Anybody watching Star Trek knows about the borgs and their cube-shaped ship. Actually, the borg ship is a cuboid of dimensions NxMxH, divided into subcubes of dimensions 1x1x1. For the ship to work, K engines must be placed in the subcubes, each subcube containing at most one engine.

A subcube can be identified by a triplet (a, b, c), where 1 ≤ a ≤ N, 1 ≤ b ≤ M, 1 ≤ c ≤ H.

We define a plane of the cuboid as a set of subcubes of one of the following form:

{(a, b, c) | a is fixed, 1 ≤ b ≤ M, 1 ≤ c ≤ H} - there are N such planes
{(a, b, c) | b is fixed, 1 ≤ a ≤ N, 1 ≤ c ≤ H} - there are M such planes
{(a, b, c) | c is fixed, 1 ≤ a ≤ N, 1 ≤ b ≤ M} - there are H such planes

Determine R, the number of ways the K engines can be placed in the subcubes, such that any plane of the cuboid contains at least one subcube with an engine.

Because the requested number can be quite large, you should output the remainder of the division R / 30103.

Input

The input file borg.in contains on the first line the natural numbers N, M, H and K separated by one space.

Output

The output file borg.out will contain R modulo 30103 (the remainder of the division R / 30103).

Limits

1 ≤ N, M, H ≤ 20

K ≤ 2000 for 80% of the tests

Sample Input/Output