10 8 1000000000
493670268 51466679 881933345 26076581 683236494 112410464 244565462 390149109 390006316 405168392
498574403 65081596 460231903 401507281 622913295 626147960 448830971 941080736