I cannot solve this problem http://icpc.njust.edu.cn/Contest/194/Problem/F

I used to solve another problem http://lightoj.com/volume_showproblem.php?problem=1132 which requires me to determinate the sum of 1^k+2^k+3^k+........+n^k （n<=10^15,k<=50) I mananged to set a matrix related to binomial coefficients, but I don't know if it is helpful for the http://icpc.njust.edu.cn/Contest/194/Problem/F .

What kind of algorithm can be used to solve this problem? http://poj.org/problem?id=3133 I suppose that dynamics and bit mask shall be adopted. I could not figure out how to express the accurate state of it. Thanks anyway