1000000 8
0 1
1 2028038
2 288974910
3 111681589
4 291303633
5 155763713
6 177741458
7 164199419