paskal = [[0 for i in range(12)] for i in range(12)]
paskal[0][0] = 1
paskal[1][0] = paskal[1][1] = 1
for i in range(2, 12):
    for j in range(i+1):
        paskal[i][j] = paskal[i-1][j] + paskal[i-1][j-1]
#print(paskal)
a = 7651106765888543281434645400776763607999404784703253523243843201506242951986478738338965851769601399435630359428096011477050689721871892538821404888205172342606934311766064744943719195105309732631081587209928704
sum_odd = [2, 3, 5, 9, 17, 33, 65, 129, 257, 513, 1025, 0]
sum_even = [2, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 0]
print(sum_even)
print(sum_odd)

for p in range(3,65):
    mul = 2**(p-1)
    _odd, _even = [0 for i in range(12)], [0 for i in range(12)]
    for i in range(0, 11):
        temp = 0
        for j in range(i+1):
            temp += sum_odd[j]*mul**(i-j)*paskal[i][j]
        _even[i] = temp
        temp = 0
        for j in range(i+1):
            temp += sum_even[j]*mul**(i-j)*paskal[i][j]
        _odd[i] = temp
    for i in range(0, 11):
        sum_even[i] += _even[i]
        sum_odd[i] += _odd[i]
print(sum_even)
print(sum_odd)

print(sum(sum_even[:11])+sum(sum_odd[:11]))
#print(sum_even[1:11])
sm = sum(sum_even[2:11])//(2**60)

print(sm&(2**64-1))

even = [0 for i in range(12)]
odd = [0 for i in range(12)]
for i in range(32):
    cnt = sum(j == '1' for j in str(bin(i)))
    if cnt % 2 == 0:
        #print(i)
        for j in range(0, 11):
            even[j] += i**j
    else:
        for j in range(0, 11):
            odd[j] += i**j
print(even)
print(odd)

print(int('9ed1515819dec61fd361d5fdabb57f41ecce1a5fe1fe263b98c0d6943b9b232e', 16)%10**7)