Input: 154
730875020 573073279 366146330 394939908 303442396 50644926 821787618 65749391 328576656 724949421 151300841 940337313 764273285 507888667 161589809 190799435 564207354 292863813 167868331 439731228 29018195 87505707 551940348 232555805 252486260 588487982 998298561 976355174 153764502 119224002 987472829 760100074 338582385 904452756 237381837 927032415 521162594 872490663 122595333 80923348 875449978 443216229 634797666 874643947 8450424 950785900 802116642 827888574 296977718 554513894 61506981 724911102 54841369 202062219 391576592 185002504 155765843 286927177 922517183 928790085 629853437 629277205 489279415 694799115 709956395 654730101 429212828 274778800 999960270 130288628 355723086 422822883 441902025 424591035 309009092 877309923 243045863 689584957 81027909 436796736 263202636 475730679 664229507 764632871 307718061 433958810 646254026 635732828 251013300 897916963 995436071 897849439 387951900 19479338 727585278 174514960 67155178 501084054 748312165 691316039 114564575 139299096 404543594 478574442 53968517 332825837 32417026 986579525 624877324 178376715 291624632 334760917 370323423 86980498 298080761 14421010 495825996 474134579 987648962 66151461 368508360 797808913 30704331 305868853 542746842 692192407 114243061 419263498 506752493 318975692 960691596 198646762 80943569 439117425 205838130 289527123 139917461 978081547 781264699 173515550 382207781 955060243 364983476 928923025 660101307 204110148 86794180 847514239 194308511 187081774 296459141 613677914 574429905 758913851
Output: 8450424