Input: 449
932032458 845367909 637679879 199616164 546911478 205685821 682687137 481905299 384807554 950737775 311474589 764674549 782212011 948133472 276981016 986078782 834957961 88999037 841258529 544024226 256157951 354537257 472101809 930147617 747293498 402566677 319203143 32319078 664029383 716975481 762499688 19210688 895833909 499978524 101042265 942783384 754475960 545752687 495504849 343481918 179477649 897561984 452963734 691654717 493219491 406462065 41737361 302815063 191157656 324160808 963378772 57307903 239092015 444353477 545230012 625506927 878341233 230934691 534363980 631527021 970560347 86172132 540487547 648597470 501002010 44951032 694211029 202870777 834763259 307202424 566652183 437173323 7916572 214436387 913561080 45184701 757592751 148445889 723842607 26021842 691689697 685290804 605054244 550450446 477662646 929197837 25664029 530587577 729286432 856315865 625440123 122452678 847738911 728291232 756619275 468463342 710779024 268245178 336598438 894255544 54684197 858765696 689875897 124996489 442272545 79341205 222160248 538669195 193561721 124699953 315445955 953033704 421264097 621896059 882396268 951457919 487341218 620376654 999795405 25699932 776118709 264108218 136729193 256164639 768284078 240831203 324402554 873730392 599288363 257780537 612740176 604753191 296483294 488736982 849659878 32389267 972755003 822121772 182235542 422217056 56386917 190957108 132457996 62782912 768399888 64339148 880748243 547439218 103117257 481422541 27041063 973726248 200498761 592961678 122550559 755415665 795896710 787027977 834347875 232928722 817436648 297463398 294845968 475342969 190219573 600834981 330433859 12440345 757162897 880901120 837772745 858664731 812534567 909973408 440135415 236600111 601757404 275425075 240300423 475496888 467221032 828654311 632695043 415670276 15675224 150430042 17094957 500048726 742505865 840194630 229153922 170091446 717593255 892671479 130886163 49460752 738792325 947748790 867546970 804407356 773467990 725862248 845277716 139534368 892328541 391357271 477270361 480826811 892218321 430043239 428469582 677699322 982862955 683735364 675824083 371320614 190413991 182786242 523730971 801463769 696333252 467056191 894210517 597774610 833939780 946143100 178197714 437684032 23729958 212913291 321540231 75988563 720709700 509401592 554570158 461452315 647615745 544101424 588394154 188688614 874022620 810766252 902997884 999767120 58243588 66699648 625998313 476930765 636915952 480390933 313628342 476306228 991453221 124862514 825371396 410255011 435543484 457573261 246065730 818497828 329606904 173652719 975233247 884794529 308361813 487619191 323532559 92261429 431199319 125849401 154129763 210099501 256705888 801363843 685512871 729144297 189889606 994363618 291217915 153392982 260512667 889233556 104939924 901435871 150242130 91859776 789433610 579913173 135585911 419656029 506430352 178980465 840504312 519208602 770650263 160495875 577200286 567562338 43401354 125831894 211917488 933035798 142922405 999610836 492717833 260295763 992977154 92214692 32056616 385195812 456616976 483579216 635700677 87261943 105506586 139551401 177234714 968563620 922403470 399884634 889882681 506922426 817753552 69059354 194862565 284473169 657880870 399915453 48178176 446294450 2079877 442760202 567270727 188126314 643721768 734850986 376926717 610901708 740996794 991664161 978610874 205796858 724961679 361919934 411458848 501514089 654351865 18286715 847553657 920754155 328744802 202079983 295307597 867537598 859265766 516081050 464634832 882268021 944593697 639590945 505792330 77611073 131852341 911984019 475407762 430278839 471754409 4951055 154161640 986712689 539023342 68034426 668423908 334967437 641264016 306821344 67094016 763252957 569005720 739234929 903481079 904487857 476359493 140236123 825402193 786931908 707339487 709319577 557876479 652484232 945106686 67018702 789023286 553242317 155493227 740389919 286308332 87517492 481799464 693381738 240829673 274257327 528622384 878229296 367367571 659973762 151512940 790444816 354078625 705633649 86765659 12373766 132583958 752560404 433014936 124503848 671140036 758004417 746113294 328914461 239875300 723369013 713194326 337946219 665971539 75237200 664480250 858966188 856257017 465014335 357062581 939706350 395185457 727533832 792813085 324633677 957913568 621518404 362313644 63718296 632920438 890442406 532472769 88115286 359166272 945425819 959539690 106478978 851138924
Output: 2079877