250 : 250250

集合$\{1^1, 2^2, 3^3, \dots, 250250^{250250} \}$の空でない部分集合で、要素の合計が250で割り切れるようなものの個数を求めよ。最下位の 16 桁を答えとして入力せよ。