Problem 250 - 250250

Find the number of non-empty subsets of $\{1^1, 2^2, 3^3, \ldots, 250250^{250250}\}$, the sum of whose elements is divisible by 250. Enter the rightmost 16 digits as your answer.



In [1]:

    
a = [1] + [0]*249
for i in range(1, 250251):
    n = pow(i, i, 250)
    b = [0] * 250
    for j in range(250):
        b[j] = (a[j] + a[j-n]) % 10**16
    a = b
print(a[0] - 1)









    



1425480602091519



In [ ]: