1000 1 1000000000 1000000000
718547640 826725493
236930928 880437581
623923115 110908772
707124059 221018124
988135211 133887509
606410008 865539368
489263099 583296563
534596534 135120593
274861484 547183493
289084696 949635296
771376634 365730758
89439673 931027281
905613866 654177654
512836986 472720839
152914304 435246210
703504262 855780351
627178652 827542462
698182613 758240813
706932251 3177804
395335004 454672363
90860427 587804568
656495630 768441885
352882774 467081108
772573422 377300773
943730846 176094560
455508406 419992900
601622577 976419710
166470795 871798597
493090045 116350045
896453518 792691650
326041495 73597584
44928346 73594983
646075477 199741822
259128037 562709491
544891019 728360170
603020990 621817264
842954572 633663229
214324798 996708034
239618539 96283195
313750011 969453898
489147 63443075
577489292 754294962
37489765 501013480
136809067 992655464
60861074 797012853
883124896 563668808
189008379 465121424
29437037 150058744
602000271 841079292
596383184 558935386
643618489 95870031
380970244 494776700
106757638 291923541
146440180 697461327
184902062 769900770
1495668 299704997
911217127 214768673
865673420 211763031
524960044 854781808
335045819 921053498
556542712 392727456
349318797 492812124
977392464 155559479
639065022 795519012
254107551 229662664
712200189 150271349
829269357 880899176
974415885 143273346
440254232 650862524
712288966 250057605
814710907 186097175
983983843 31948567
944886546 61254197
735264512 890761693
156171813 769190164
602976676 946059158
127194776 292948495
189910958 347837107
484251361 571584633
40305003 901808582
442168065 2229382
951099412 988103038
572827352 366073532
597968791 448985569
293149017 160672075
105269009 36989582
233538502 902802947
154164004 609663276
698537179 125893905
402734152 67085926
902116548 327696860
425862545 917672253
254849699 274512404
501809442 768935126
418795866 788043342
447907748 243325984
113698930 333205385
301657777 163651902
256004900 496390893
58206706 14635563
206848403 353338109
403931214 921822639
978770353 36598882
562389797 779257910
751360072 740442937
17688242 864279699
36741598 364831424
166346848 790679705
145947351 871907185
427735161 37724833
81469320 783479315
211338392 447647056
729999997 614545194
483453340 981809399
878549023 147439926
723919600 967608728
518348486 488300970
433338186 934161862
541466529 699880331
301703478 632948567
947687043 313148031
829889706 755985836
252459205 228554220
896029009 313040554
874676100 923323434
160158636 303234819
855433193 683938443
623888981 735667767
551096487 936353250
319166131 817002488
706953507 6900406
344011289 158104313
68029236 623897073
36579120 661650331
953550368 676302772
365776587 671167107
808886432 647259476
891437446 400327109
967061794 405897311
324694196 358802225
780220129 792486613
605393020 764917538
14458940 495054983
954447276 931278293
299587864 868286500
891835226 551090345
364577305 569324716
213057286 251817292
411354937 614581810
256440944 848998665
941403459 834508603
979506865 384500848
574165109 810324336
794101548 306318594
322043510 511886587
327199299 405548029
617912996 766270578
207843365 312694473
347226084 822418991
201921799 240568334
703402961 41738237
987272082 93292349
863169191 744200591
184518919 217151506
34480877 533933698
927235711 704045812
145866855 780135204
902271439 855163514
370276716 54260908
941814733 832311279
372327992 141745125
568015170 656375931
964297455 128092357
434412137 124032547
98026577 80225001
72323130 300563686
417461361 32803187
321630113 482147306
75798682 577295109
31613687 706964045
73766289 23439776
176784244 410851087
908648546 246104246
203836236 877997433
10136180 286214430
858320067 16466913
967402411 86377813
723425112 306408556
376091513 407088166
419060986 718051789
723875380 688201955
678501462 997494067
824241018 46023847
54130524 69503935
151193177 585279936
655841878 834840882
39193535 67062263
338556023 349817467
125137185 721192240
12921659 101006982
920340455 590194054
29974912 739264109
823857757 411137220
801379612 453834445
803060750 303070698
267528761 966664259
968027324 756824391
462540393 554592189
213252141 898918073
84944387 286542587
369481383 203637823
643169425 845903758
41693554 691586451
773965334 524846129
663622047 816882356
738424514 685423284
697595534 299491051
783711133 718035703
289335366 897870714
59007327 155480574
754796881 787267636
522205782 562744204
749900193 760804868
840806979 389424077
839417313 807287919
638230975 491828228
939342962 847850345
667867020 182148320
24377542 92749863
104823660 697522245
850919262 872497465
263296182 985300160
794049690 119878278
700151556 833537353
297879703 350248830
17782323 126916103
721402573 878841437
287164353 445329476
371404076 700867652
71658033 240750645
360357879 471309722
630332339 401394671
236564445 87866902
244005473 442313498
497674898 687152643
355948318 728332018
524404281 298614460
611077043 746641322
831532987 803590887
61882668 288547392
16697401 262374888
76347558 587087396
348082505 597190352
513345531 681854202
539676962 253803646
845802668 64920513
152586558 962405442
323124142 600860047
984001385 435854954
324607326 736282150
278377414 589949218
507927360 624910977
150450592 158759798
585087148 326058821
44703027 874088294
836883571 98497933
684322540 350675867
220994622 747484274
863640685 590030704
943902146 307412698
706226585 410806569
99321106 201794086
6606335 910895251
762522732 639573540
872946772 247231527
248454711 934012938
732589707 18321191
960040710 797323515
509274698 489386320
880273147 428962743
353096954 901597386
697111197 414137225
140188181 449074520
333799721 445837525
262884018 937260413
219698066 621054633
222478522 104090395
549339717 310198871
700915576 494431368
502148481 206793363
125905686 234975945
534553467 309003470
22585918 120731490
403337559 20373683
446187332 858131299
167711458 867282160
562089705 829436986
572241752 176223251
545604149 267442745
598415912 424347668
742932112 630603770
644963712 439111449
811730531 321788024
452362323 572916054
954919413 727213147
112145359 889895984
500776204 97223832
24253495 76284676
857572642 731959776
603870004 602947226
189250934 660355753
651767693 836717324
192758512 851123566
238568426 602248585
796141067 513336203
503521594 752444959
893433351 229037466
113107835 805554021
857513159 211131226
85257748 671198316
260747370 549983420
973156763 14616610
236436565 758142352
871025371 324946452
248358129 553919087
596082946 264384883
733343365 653964993
599912335 213523118
440653656 338258210
443055346 5196498
125420639 877010186
943925240 894080653
140687205 189997861
692685521 659381581
8356579 669911812
448903609 28818912
93977233 220806078
855457604 67320911
439738570 722086710
877893213 845194539
765927710 262253741
786360229 217886918
790627880 232510440
345192655 370823746
763475464 319194828
62547787 444328305
400312181 379716741
919326384 919549511
945672792 376369516
373522468 959041877
598963683 926224071
694486377 825651986
3265184 506624912
783242631 199308000
413907249 41037886
682523783 349938660
803925498 38718486
466727035 960948916
807429354 936572671
261360892 14458689
597657568 8489616
798138617 708001974
607535408 585283034
330732860 361843564
255983703 239254967
472995502 763882594
387789440 606488451
772457666 280784152
78882177 175603704
684071013 313144663
428346760 395321634
289971855 590911903
345042320 29338897
238708522 272828828
547516742 703425737
210658673 538359894
703856400 887131771
904691013 128521978
31669466 174970971
374534285 217537117
711669051 176525747
202469339 772634014
111026480 791756489
804146785 705157307
300156564 290247557
323467170 231030834
429852554 787608730
453081823 869321359
731309910 228353034
847344721 919045251
741791810 354982710
964257689 399460231
641346949 833555454
455517408 729020395
624568211 385618068
34231797 592203015
104980799 567154662
893889609 818922939
352996943 562296996
676029538 823742711
261822969 801305491
24677849 445196327
195229781 350196461
400545567 441030004
938301348 287934337
925361679 562906981
304384100 824022492
95356619 12133180
871324759 805433003
642214698 202369270
66181751 811059569
169824041 490360148
594027316 981329321
386532122 823817853
232950578 530463483
356653270 867246306
779277421 942454277
673585459 950328813
425317947 765571370
412616557 316269832
853237750 753695773
147498847 384073794
615152153 618697879
844934300 662163784
989114185 572249394
609655701 222124207
16784218 66831816
704849405 249952214
170333198 66346909
73908384 705405340
408269086 861842850
436218169 933345286
872738726 925763526
508777652 658033049
280421824 800253251
744480221 953886244
57001203 225975249
294992726 904148494
368590977 25324856
460159158 940250847
585282893 998657954
326136856 585499232
60607812 818156864
411084510 121357727
880305325 608290206
110827364 745397746
894076714 284685312
388814813 117455925
630316097 437942025
196773147 893321355
857148606 451920394
397280553 350113684
610053961 946902244
730216759 519300204
489145771 549453160
505454873 195040379
235662611 378617328
988682183 688372894
840883075 671208361
790898938 490931276
300605183 269484874
280613514 912772100
199257105 587615580
57317969 913032641
449983027 437365325
692403813 473135345
106651322 209816076
236802974 21882516
342263880 313245729
781477475 239918900
612931895 95218089
646222311 505690292
120276130 320309687
463503487 832325616
886285435 427658654
557266228 249076038
767427421 501737974
22481037 644440278
278876390 105625299
860936642 381398329
160457421 751884584
384353002 866898902
694278486 928436309
959813445 384657165
146636111 815043300
537966879 137301209
635861089 382973553
405217692 673966350
771170561 681840192
261616808 863708301
628787975 202507165
211431104 802847532
859684674 135357744
119064401 582950418
803012535 694346722
225420377 591105922
520987969 977416647
25850126 939102412
300630016 814498832
408053830 24805502
776951034 900011592
554871094 997367447
828173945 105206384
391587017 735869365
449156833 57717711
549615135 644742184
112920481 905190011
218232967 233088638
636098619 143954624
544105109 771219586
241990940 692607650
735921798 826831223
600046776 177315391
950521484 773918237
864019380 27193357
729893500 366499475
649308454 263737923
968635258 681409912
15378627 320731892
502556740 492793647
649455443 316116774
695597355 856649936
896434710 583970870
279085629 96095845
126197295 85023532
970294717 804297695
268026275 373267604
512515420 67796971
532928236 882524307
73397353 81847446
264342017 391713057
889637203 233146997
147578035 65653190
522384662 693872421
325595841 587170670
597780695 562216695
236248466 686920795
850253458 634818020
642375941 133613103
202613301 369816772
575218663 716307389
437274101 438162669
973270588 382335264
308372688 235728164
158254162 892510344
177075302 688397792
948349982 726067320
24489172 803355078
932755992 570786029
1502146 457161108
3310060 331706655
146343265 447920151
706137795 900546527
63105996 535990290
902560740 866333117
872942824 44578920
942920429 287941894
679788974 155546857
404267644 666367148
830593279 712338634
33385159 376978991
983039788 604792946
996332867 281175735
149173483 461424215
756228032 717298212
579361737 793486456
789526989 960126429
346418809 129741992
80509656 877549780
433907784 337492847
592461008 446034996
815652166 858349684
156296098 10381551
616001653 188794702
912813518 388147545
783692654 626348869
328738254 778370616
508137976 180712967
130204950 794243339
708210670 42374019
276938539 109801293
573218548 113736596
368337289 204139782
217587336 672859981
926805347 469012382
799195856 168490143
657494253 685826357
861375147 676527616
616197292 198106941
495959080 499751656
823223449 330649692
135745851 410035082
101010775 15138061
206211823 839066036
162998605 655417114
475850589 971500105
382466017 938454511
110254915 813381842
379886546 206981509
165806427 356606365
8698253 747710390
454001674 473272333
430720133 708815478
407062430 16264931
457862320 589113251
210217084 216684346
916004928 289278212
107187537 125309536
445310470 485805468
394886405 892791434
389763963 687723726
303661523 798462229
514004778 323843945
203782792 375410489
499751495 847294479
521039411 822813815
65177087 350063560
408717576 306573881
181943230 972189663
774898758 215321265
65350985 340180049
258620905 28231991
227937048 952392792
382268307 59332114
26191896 373808376
467514500 943693770
419874821 40288521
215775546 625903663
495252885 587642907
739602393 680295845
84722486 801293932
547539786 743692633
218535397 368866048
681119489 460923410
358222090 654574862
168876441 745448691
339885651 197922306
879241954 34389064
668556097 770113117
43167234 89653145
487599031 753115057
390277421 363308459
950740794 694835770
351790136 932601842
365206334 949053597
872517086 22994529
884992206 843213040
426791896 509239193
511267319 296798384
123545876 926024808
15784504 906676542
729025089 170307975
222098560 345622674
837470841 554519214
953047408 311405047
726760662 318887473
241714166 994629100
984442085 355798450
982925730 85470165
257326033 291150242
714859500 147030004
333004534 336976011
322750656 884029711
713107853 434175639
71869576 520720680
285232948 180169582
943349037 465201803
183297604 247916083
968185391 425845014
375266632 392400428
351543449 609448054
504047264 478919781
136713022 973373256
493774359 102882206
976672364 331739559
22241356 480171511
27811826 488282050
144044088 125283399
837186361 248474652
761880711 984420834
409549731 866747094
809806115 813680457
976852823 130062750
597112406 677624947
679965084 238829166
820562370 58301450
754828172 995283899
982229332 604641162
503426129 576454518
937108624 490792931
449833227 584978960
766501955 491061864
524780756 821060999
248100429 598625485
795893847 690320663
630493890 523092559
337840691 696101541
867927692 984386237
5585583 604861109
720551934 991631471
588845890 616666977
356826849 448089440
556447610 919746570
129450332 477216942
80906456 11810463
746073617 919269052
517207807 987935782
973708034 929266710
12020934 934726102
544263460 520500034
472687364 645953209
951886848 76040954
27121454 51754659
125100857 205127904
169729918 200654100
433217368 91018792
593697701 973259576
452782621 479368901
851226718 263673457
322188697 336885752
320903285 417736840
187974507 692575944
871285951 747676332
172277003 310087539
233649636 885092498
835544453 259348324
591820851 226222216
280777012 616913219
686044117 355842016
744629849 963295967
749307841 903001554
786739625 926328784
552630602 30055903
452280270 184651837
450192476 636397784
115307885 365289851
571242338 273196409
73831220 492558907
704397532 821773555
464282591 749020057
227878463 745560368
186328437 547740937
938614158 446575130
412537940 371749565
371867123 157863583
925736431 672399077
244533558 302294281
144946592 822665832
828679693 217572475
824328930 761559167
211903226 162522299
234762667 437336696
638112156 108909025
251573028 433727399
72268349 717776032
401950212 546623572
187151280 284025328
189982840 448594803
536485522 195471226
174733755 643110404
429694768 433664436
476832591 455663870
147572502 887363691
921686609 949331825
589396152 252694423
573283051 80053404
190184273 256974192
292961683 642591768
227256726 19222979
384389374 200370513
198982288 905958219
711808572 167921624
322188403 65570088
646622385 28421487
890390280 441077163
191309814 653734802
60622945 935196727
923949495 261666075
905706616 202372665
416308213 433992427
360344545 391757760
309185415 146702553
98269732 888341290
726786239 76202643
764074351 474767584
514236953 765703703
223349734 345351948
366497532 116333874
229937044 480937346
151030232 237606732
796665845 176243791
119439633 909730171
518791155 91062893
654322700 811992868
575905889 366987666
246796117 621374581
332506397 859412907
478266404 25975292
589350619 830489481
458265355 399354308
92622790 935887016
910503042 193046768
886682223 623059162
504232217 202139241
265427993 200783941
90735369 497721253
219282925 601764205
859028061 583293225
437340755 957840117
595133598 880936475
670806133 459832120
880563450 976495274
923590002 953269473
253599522 718567379
853529200 402461398
777907065 669255745
553530622 766855399
703825080 19033073
661973356 206845920
695923382 705470280
417538564 555716254
554246252 495862770
732502992 47913057
234870706 414962165
783279456 722186048
927407132 407219023
696093024 265221025
762900244 132421542
93246492 324322273
585913156 496759324
31179589 196656348
950685965 938657744
940814882 950873142
805066497 718850032
824485950 311017629
59954020 933838822
188661781 342106857
649440706 686029309
29942009 134267109
651469600 635400137
941252082 253725757
335065742 937748646
879292377 883176825
543078167 582561729
912192141 933158608
914558600 196805302
942714583 295291498
44687013 124901980
837604933 105844533
609448799 753510839
963745455 875575549
724612220 674192858
978281817 553692414
732112060 997523734
40390 667807038
220505137 406709924
426217569 208719951
289139577 903406839
589966688 702726531
898111513 517488005
885236944 181946794
38634318 968353315
634758773 475144303
482405574 648501330
830772594 300936565
985839889 699157442
436939606 158654532
138180289 39504671
470455689 538952831
44671542 250389546
867939230 779300498
860964232 283279895
725032214 184514439
867132944 226867062
951317908 238480084
454174435 306290116
528219423 722205928
648266459 980896617
242727878 900576189
814703724 341251452
104468519 173919040
51198657 958394773
263724332 442242014
726680100 209890222
525201188 84271657
265006919 777877914
903762775 797966423
871924759 192161201
766939182 424770842
607547020 762444588
143196486 330489978
305674435 122460398
698847689 438356922
16045637 587256376
669814345 804837488
217422799 123873604
912564819 849285890
230175803 553656226
962435915 351178266
399274715 568259788
73791077 922877731
465497397 755945979
197307138 364420583
477996212 432976222
522964254 575478559
899558801 67977615
896516640 207392131
631982094 214310037
181446763 107054774
348619933 444095583
582379196 659653612
210652185 953188713
430003947 157157781
99870921 502600387
827709402 285437881
401326236 730499843
517953524 169568094
982184755 739786383
999135268 281902392
847416635 197358268
234217833 991747975
407856310 8739611
679077904 912827998
911817069 319916579
25612138 232302093
298444172 89464231
221750120 333092490
100654380 538822707
483053817 652965937
519745825 275539011
149503257 465692522
15109927 970186194
132978800 181212120
694100744 907388067
128078183 605782964
82805802 107922521
769103189 95384930
32630050 693382924
72792903 595147949
235290318 726602688
138769590 556343878
135685439 477375720
532425821 735713248
644446281 329443073
658469185 937917237
546694136 834896251
873530268 92154915
608184566 537828366
974732205 343036933
212750724 510128311
945142425 471354424
684574623 276768235
609430970 283246424
904720712 241913635
842321382 160395880
213602592 474946159
632641248 746343539
80284845 969414530
106686616 454996146
437036741 268526693
291559275 780240549
635267106 756699138
203094717 116704095
529419061 374645236
790573275 280694053
481753560 30396023
393823792 159900457
986990840 383512184
965439946 886377589
915923130 885697654
195110504 788575083
986399171 207321173
423617906 756840178
294175546 283375134
445611276 878053747
521320364 819658907
833161656 537214319
623055698 934099307
642335773 128291896
352675312 720871917
434181203 998107291
286637766 546246279
606827304 903048117
66900935 272853358
519724018 679929896
284446483 899498086
732841365 813195374
826780853 160970811
587037587 367987107
33657010 898932162
36500123 302623365
720627553 761363842
95522371 377975408
1228920 362925978
980877162 851630699
968147318 118597899
284286544 441101908
174793893 803086120
579193424 925400889
625108306 571668910