### Problem Statement

Let the function F(N) be a number of ones in the binary representation of the number N. For example F(279)=5 because 279 = (100010111)2.

The sequence X is constructed using the following rules. The initial element X0 is 0, and each successive elements Xi is A * F(Xi-1) + B.

You will be given integers A, B and K. Your method should return the XK element. See examples for further explanation.

### Definition

 Class: KthElement Method: find Parameters: int, int, int Returns: int Method signature: int find(int A, int B, int K) (be sure your method is public)

### Constraints

-A will be between 0 and 1000000, inclusive.
-B will be between 0 and 1000000, inclusive.
-K will be between 1 and 1000000000, inclusive.

### Examples

0)

 `0` `12` `5`
`Returns: 12`
 The sequence is 0, 12, 12, 12... and so on.
1)

 `1` `7` `15`
`Returns: 9`
 The sequence is 0, 7, 10, 9, 9, 9... and so on.
2)

 `15` `21` `500000001`
`Returns: 51`
 The sequence is 0, 21, 66, 51, 81, 66, 51, 81, 66... and so on. The sequence has a period of length 3 starting from X2, so the 500000001th element will be the same as the element with index (500000001 - 2) mod 3 + 2.
3)

 `79` `4` `700000000`
`Returns: 478`
 The sequence is 0, 4, 83, 320, 162, 241, 399, 478, 557, 399, 478, 557, 399... and so on.
4)

 `293451` `765339` `900000000`
`Returns: 3993300`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4622

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7228&pm=4622

Andrew_Lazarev

#### Testers:

PabloGilberto , lbackstrom , brett1479

Math, Search