Cho ba số nguyên không âm ~n, m, k~. Đặt ~r = \left(2^n + 2^m\right)^k~.

Yêu cầu: Hãy đếm số bit ~1~ có trong biểu diễn nhị phân của ~r~.

Dữ liệu

Gồm một dòng duy nhất chứa ba số nguyên không âm ~n, m, k~ ~\left(n, m \le 10^9, k \le 100\right)~ được ghi cách nhau một dấu cách.

Kết quả

Ghi ra một số nguyên duy nhất là đáp án bài toán.

Ví dụ

Input 1

3 1 3

Output 1

6

Giải thích: ~r = \left(2^3 + 2^1\right)^3 = 1000 = \left(1111101000\right)_2~

Input 2

44 33 77

Output 2

400