6895211

Maybe you will be confused why ans += dp[i][j]*p here. Our problem is: try to produce "x" and find how many 0's at the end of the binary representation of "x". Because j%2==0 (if j is in binary representation, you can see a the last bit is 0),which contributes a zero at the result, we add it here. The operation of "x+=1" will contribute, too. So in the end, we add up to ans.