Input: 590
1788301 46028273 257179439 157265790 145894276 36313767 616889009 684407669 497592791 81574297 601019281 269388200 5918282 796312484 869735624 257021944 770717874 685828954 415580886 1104007 915230151 502002952 461695712 769406921 927802499 965667406 141890748 452982679 684082373 356507078 97357750 744044328 583304219 164888265 300716553 254632099 285697107 748048748 132405312 924112340 975981891 634563922 474571405 155952317 738936142 778300160 631189586 423974152 185589714 312547870 882559931 150802956 956246431 810220882 167531479 214174086 339870759 163333304 11422148 675682579 157372520 76319720 282297980 897965442 437171000 91650286 581911920 208227952 767884136 33598603 140800188 290051748 698830131 90008578 673257373 853746802 315789690 431964875 840214563 200828610 705959512 41746328 217765512 264800916 143321865 227316758 821032174 296827885 733465291 881290158 627931932 488155426 792178981 970466346 216030767 666019490 798098054 787942489 472557282 490895764 503312344 310578924 459246346 735079173 806877442 417912961 816205831 863631660 244601502 836431679 537959020 602858514 751450358 723335915 428253110 299695177 548086936 66509699 842561981 616957909 182703965 973058334 386863123 304535537 80502486 100330260 634730165 197623713 957895119 967903636 159752559 985946809 492780637 40389834 765714088 512008744 348947436 447828245 706545306 753159735 614445575 907329068 916684405 512921044 788993353 235195098 227281059 849041007 494652466 408527744 628066866 375134466 941009986 190495614 556608820 492369964 673417626 387850100 994535729 857220089 881695485 510224371 137645047 59416169 393941600 213799694 593243204 773394233 446757797 337181690 424814961 370578425 995705956 414695941 849677542 721913840 199532724 406433151 981422359 484540992 878735912 632009707 52340886 985717200 494982896 712040369 828603747 503676465 956387461 866514358 403604752 847296382 468161005 446769180 444552431 558640067 472744268 904729518 795215657 740169512 676616839 196124111 491611164 701744959 314055863 298047520 533454526 396969129 781671295 256923671 126513812 163880899 818633641 498709077 228260131 376243210 429703370 985847034 488011909 681684913 247652400 247055086 337061446 789614176 358500494 964703663 851772770 342143522 776850371 923512639 264713682 527729784 89398800 84276734 478216175 791472756 388025197 467845317 154291347 494123055 49110373 920344995 676168237 993807388 865230200 23354372 871297125 180048050 714096913 527993389 380514046 903271147 132715407 392715718 433015276 267934012 163347022 714432233 351979835 314380587 241507649 901931624 81039557 261184912 936289033 969664245 478844270 836879527 571729284 161921673 358138223 54990223 937501917 683399614 825234031 704514082 233013433 256262136 870109069 288715030 19424250 657690603 570300866 942596176 53099046 362271186 63907793 233405940 386515342 519659212 462778773 758114758 661432436 371021125 45366043 631453375 235963898 796805249 767169708 741372790 670734823 858286708 373238639 751026299 62242637 704668285 499269686 131859688 328337803 394733950 563440642 326062423 380231888 551498310 702063037 785819238 540752007 783421587 537189433 451283966 531601033 639908422 235960784 84556287 217208766 105422618 918387695 372200007 700036998 940420192 664848991 131886125 671222411 334746475 469918846 222172953 351911763 679202866 606604333 237143577 269182871 385963029 839158207 337697260 658889491 919584329 106171885 302166467 745757011 135914334 668187879 666158868 602362712 956873199 155035908 65056449 954520782 438636109 319903565 245489214 910548630 441094381 548761986 935569527 730130255 96014026 975283114 840502873 161483596 660641151 431666417 685614048 850089570 969495442 764912448 51818312 317206659 53610684 421598635 801570321 616106702 534251207 968404953 246691796 90418044 215878065 329295936 774492997 97657205 222218371 794142860 772384856 189967031 355521454 406338976 78640655 242782539 203110076 124800563 659417096 868335537 37409617 184837744 892505914 580584546 749434302 100972297 571951315 309103382 684569808 459482584 169958992 358675623 107026273 310543595 755637681 790915729 350388605 863100221 324824568 244337384 482009768 987605172 437908608 625621420 20084806 182403663 22766008 560713681 308147878 657021435 679492250 53905461 231748606 305778621 3026209 469164754 599679377 410946576 961031196 444818663 350131171 781468014 989973188 557055519 590423154 236426838 817774946 964526320 102955801 783354490 927891470 333070950 163672219 669329275 195515536 904834779 942832343 166157588 918463729 632870892 765100205 827040857 215848343 570831978 260453120 378558906 888329038 423654107 684521690 388687810 698719149 261749744 939111514 564164148 719469134 423691938 650248129 958170286 733577869 982645599 526772947 18086611 271443517 924200779 409731229 781538281 364642212 598493926 91064760 958436148 543725035 20599094 303034917 983200635 598750126 103030028 456887471 702451810 19287080 925335709 241723473 830129508 515142034 788534878 37595607 80127245 467584460 525637544 508278744 504041787 773602897 422781870 80258515 545429936 561459719 511493927 956788632 930339264 651323209 545854974 113905181 224721913 233410840 573160779 986488181 598746883 90872816 844511587 783750782 135597569 119341820 342785561 62606848 526617897 207507164 697763091 291335381 30829836 183422089 225429535 834577574 126401137 379669619 377363369 162284941 891731700 982238224 780280520 689686192 661631879 374353272 431852458 761522741 110126841 202862325 485144020 603972967 864674760 256735818 324511803 828585953 192266452 716646511 828381798 689200242 353664188 724321219 469614665 851166734 222459957 695904769 253046263 115233523 151135183 319502373 197525091 488360929 84800333 662053380 43008046 520116983 100779035 568419404 419688578 259223674 856423279 256031276 361932562 226187781
Output: 1104007 1788301 3026209 5918282 11422148 18086611 19287080 19424250 20084806 20599094 22766008 23354372 30829836 33598603 36313767 37409617 37595607 40389834 41746328 43008046 45366043 46028273 49110373 51818312 52340886 53099046 53610684 53905461 54990223 59416169 62242637 62606848 63907793 65056449 66509699 76319720 78640655 80127245 80258515 80502486 81039557 81574297 84276734 84556287 84800333 89398800 90008578 90418044 90872816 91064760 91650286 96014026 97357750 97657205 100330260 100779035 100972297 102955801 103030028 105422618 106171885 107026273 110126841 113905181 115233523 119341820 124800563 126401137 126513812 131859688 131886125 132405312 132715407 135597569 135914334 137645047 140800188 141890748 143321865 145894276 150802956 151135183 154291347 155035908 155952317 157265790 157372520 159752559 161483596 161921673 162284941 163333304 163347022 163672219 163880899 164888265 166157588 167531479 169958992 180048050 182403663 182703965 183422089 184837744 185589714 189967031 190495614 192266452 195515536 196124111 197525091 197623713 199532724 200828610 202862325 203110076 207507164 208227952 213799694 214174086 215848343 215878065 216030767 217208766 217765512 222172953 222218371 222459957 224721913 225429535 226187781 227281059 227316758 228260131 231748606 233013433 233405940 233410840 235195098 235960784 235963898 236426838 237143577 241507649 241723473 242782539 244337384 244601502 245489214 246691796 247055086 247652400 253046263 254632099 256031276 256262136 256735818 256923671 257021944 257179439 259223674 260453120 261184912 261749744 264713682 264800916 267934012 269182871 269388200 271443517 282297980 285697107 288715030 290051748 291335381 296827885 298047520 299695177 300716553 302166467 303034917 304535537 305778621 308147878 309103382 310543595 310578924 312547870 314055863 314380587 315789690 317206659 319502373 319903565 324511803 324824568 326062423 328337803 329295936 333070950 334746475 337061446 337181690 337697260 339870759 342143522 342785561 348947436 350131171 350388605 351911763 351979835 353664188 355521454 356507078 358138223 358500494 358675623 361932562 362271186 364642212 370578425 371021125 372200007 373238639 374353272 375134466 376243210 377363369 378558906 379669619 380231888 380514046 385963029 386515342 386863123 387850100 388025197 388687810 392715718 393941600 394733950 396969129 403604752 406338976 406433151 408527744 409731229 410946576 414695941 415580886 417912961 419688578 421598635 422781870 423654107 423691938 423974152 424814961 428253110 429703370 431666417 431852458 431964875 433015276 437171000 437908608 438636109 441094381 444552431 444818663 446757797 446769180 447828245 451283966 452982679 456887471 459246346 459482584 461695712 462778773 467584460 467845317 468161005 469164754 469614665 469918846 472557282 472744268 474571405 478216175 478844270 482009768 484540992 485144020 488011909 488155426 488360929 490895764 491611164 492369964 492780637 494123055 494652466 494982896 497592791 498709077 499269686 502002952 503312344 503676465 504041787 508278744 510224371 511493927 512008744 512921044 515142034 519659212 520116983 525637544 526617897 526772947 527729784 527993389 531601033 533454526 534251207 537189433 537959020 540752007 543725035 545429936 545854974 548086936 548761986 551498310 556608820 557055519 558640067 560713681 561459719 563440642 564164148 568419404 570300866 570831978 571729284 571951315 573160779 580584546 581911920 583304219 590423154 593243204 598493926 598746883 598750126 599679377 601019281 602362712 602858514 603972967 606604333 614445575 616106702 616889009 616957909 625621420 627931932 628066866 631189586 631453375 632009707 632870892 634563922 634730165 639908422 650248129 651323209 657021435 657690603 658889491 659417096 660641151 661432436 661631879 662053380 664848991 666019490 666158868 668187879 669329275 670734823 671222411 673257373 673417626 675682579 676168237 676616839 679202866 679492250 681684913 683399614 684082373 684407669 684521690 684569808 685614048 685828954 689200242 689686192 695904769 697763091 698719149 698830131 700036998 701744959 702063037 702451810 704514082 704668285 705959512 706545306 712040369 714096913 714432233 716646511 719469134 721913840 723335915 724321219 730130255 733465291 733577869 735079173 738936142 740169512 741372790 744044328 745757011 748048748 749434302 751026299 751450358 753159735 755637681 758114758 761522741 764912448 765100205 765714088 767169708 767884136 769406921 770717874 772384856 773394233 773602897 774492997 776850371 778300160 780280520 781468014 781538281 781671295 783354490 783421587 783750782 785819238 787942489 788534878 788993353 789614176 790915729 791472756 792178981 794142860 795215657 796312484 796805249 798098054 801570321 806877442 810220882 816205831 817774946 818633641 821032174 825234031 827040857 828381798 828585953 828603747 830129508 834577574 836431679 836879527 839158207 840214563 840502873 842561981 844511587 847296382 849041007 849677542 850089570 851166734 851772770 853746802 856423279 857220089 858286708 863100221 863631660 864674760 865230200 866514358 868335537 869735624 870109069 871297125 878735912 881290158 881695485 882559931 888329038 891731700 892505914 897965442 901931624 903271147 904729518 904834779 907329068 910548630 915230151 916684405 918387695 918463729 919584329 920344995 923512639 924112340 924200779 925335709 927802499 927891470 930339264 935569527 936289033 937501917 939111514 940420192 941009986 942596176 942832343 954520782 956246431 956387461 956788632 956873199 957895119 958170286 958436148 961031196 964526320 964703663 965667406 967903636 968404953 969495442 969664245 970466346 973058334 975283114 975981891 981422359 982238224 982645599 983200635 985717200 985847034 985946809 986488181 987605172 989973188 993807388 994535729 995705956