C. Unsuccessful pseudo-random
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hacker Kirill decided to develop a new random number generator. To do this, he took two large numbers $$$ n $$$ and $$$ m $$$, turned them into powers of two, added them up, and raised the resulting amount to a small power of $$$ k $$$, and got some number $$$ r = (2^n + 2^m)^k $$$. Random numbers were supposed to be cut from the binary notation of the number $$$ r $$$.

When Kirill posted his ideas on the forum, one of his colleagues said that the numbers obtained would be too non-random, pointing out that even just the number of ones in the binary representation in the number $$$ r $$$ is too predictable.

Help Kirill verify his colleague's statement. Write a program that uses the numbers $$$ n $$$, $$$ m $$$ and $$$ k $$$ to determine the number of ones in the binary representation of the number $$$ r = (2^n + 2^m)^k $$$.

Input

The single line contains 3 integers $$$ n (0 \leq n \leq 10^9) $$$, $$$ m (0 \leq m \leq 10^9) $$$ and $$$ k (0 \leq k \leq 100) $$$, separated by a space.

Output

In a single line, print a number – the amount of ones in the binary representation of the number $$$ r = (2^n + 2^m)^k $$$.

Example
Input
3 1 3
Output
6