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.
|-||A will be between 0 and 1000000, inclusive.|
|-||B will be between 0 and 1000000, inclusive.|
|-||K will be between 1 and 1000000000, inclusive.|