Ở trại hè toán học SPIT, Phát được học về GirlFriend - một công cụ rất mạnh để giải các bài toán tổ hợp. Một trong những ứng dụng của nó được sử dụng ở bài toán sau. Cho hàm số $$\displaystyle f(x) = (A + Bx + Cx^2) (1 + x + x^2 + x^3 + ... +x^{10^{100}}) ^ 3$$

Với ~A, B, C~ bất kì, hãy tính hệ số của của ~x ^ k~ sau khi khai triển ~f(x)~.

Input

• Dòng duy nhất chứa ba số nguyên ~A~, ~B~, ~C~ và ~k~ (~1 \le A, B, C \le 100~).

Output

• Dòng duy nhất chứa số nguyên dương là hệ số của ~x^k~ sau khi khai triển ~f(x)~.

Scoring

• Subtask 1 (80% số điểm): ~0 \le k \le 400~.
• Subtask 2 (20% số điểm): ~0 \le k \le 2*10^{8}~.

Samples

Sample Input

87 37 91 2

Sample Output

724