1000 2000
333 228 718389176
796 286 323493090
743 43 751876815
128 554 175625940
931 997 418408353
941 760 543284679
993 804 616120905
697 489 213909773
910 56 472309842
950 476 64495844
142 419 757592473
635 199 204072319
777 616 142052269
872 380 690960817
765 604 246429343
128 654 276155495
577 527 373439677
76 16 633138779
765 591 795963426
887 286 906085879
225 65 214357167
279 215 12118505
673 609 550193421
422 692 294439003
826 309 627718858
716 537 381651927
356 425 80228650
379 836 807295110
562 631 941822558
812 701 415825725
717 361 969412609
468 27 21778825
732 612 376633696
261 215 4629543
392 422 239795144
718 587 93432050
999 634 984715610
608 739 115616201
719 222 614740164
331 516 955960826
281 23 136442634
901 633 706731340
36 915 601622710
534 334 387756468
633 443 519654867
129 27 942463851
784 906 654369832
752 823 731601359
311 281 665128457
189 313 186711221
400 258 185080796
164 880 936577567
945 983 267870501
260 831 89797942
167 315 599495345
139 450 236218361
856 118 285855414
331 354 486816682
74 16 644042486
93 647 136313893
392 570 787014333
671 353 73152874
817 495 454459832
200 546 185046435
89 40 976400704
512 751 732612230
360 947 727027829
298 264 116130300
556 323 33387256
187 536 769483060
85 876 648936167
989 498 282158210
643 291 892497140
490 822 336483045
328 863 780729528
30 627 46895289
146 163 512419220
939 359 787705339
987 429 79027856
662 983 139326112
119 136 488627836
439 709 952554442
397 968 908541875
402 774 864309461
731 430 131904795
91 29 349784873
629 826 313994685
413 349 177540309
734 70 561219206
135 725 893886558
372 453 10057742
424 930 288332428
26 230 187493681
476 506 446780774
155 678 695912772
355 905 628660786
584 974 297556839
174 430 321605623
396 769 535257173
526 460 736941215
232 557 662611214
898 40 750161754
400 10 670622100
700 665 73958242
685 708 209386880
335 901 618640447
689 730 378002253
715 107 343641782
589 695 502319187
929 204 849833550
783 45 66146300
773 307 278953157
444 241 931248405
589 502 582579246
711 99 871562591
542 326 835338123
180 376 289386659
227 148 533315797
324 782 352197942
346 374 861011850
845 793 45626779
352 28 291954818
449 856 393657885
309 839 633935633
389 367 111302121
69 758 676899269
647 290 525281800
869 313 734133941
332 200 169556246
507 702 446581597
306 781 653017398
266 40 950088319
149 820 898082535
810 578 340157616
199 462 365680386
20 69 662749956
195 87 452313986
546 124 830785462
501 363 936079239
369 949 912165
184 254 592426877
279 34 476003457
507 12 694968149
623 135 584594262
744 564 227666218
277 582 272672379
883 47 921523286
199 912 78225770
447 482 963410982
190 375 502781976
106 370 27548562
210 149 429425324
445 705 235807350
298 97 901425317
848 198 549067551
994 721 981044206
327 553 533032665
777 992 300070643
638 324 173011307
977 108 570781505
843 201 136491318
330 800 46658183
236 420 610081443
971 156 464107277
890 345 144278530
199 703 190760480
142 116 903878833
897 373 476313339
161 282 805245717
605 12 523766202
517 57 246856329
986 714 547635410
854 280 738528091
582 260 510740250
607 576 773768697
370 165 186775290
812 61 605721987
566 383 166988762
230 43 156805804
104 157 950938801
758 741 709281118
968 852 498442300
170 483 738549296
593 795 396813245
339 287 722212968
601 805 683314725
974 275 477647018
761 1000 905553737
382 306 112262178
814 543 767550895
314 911 568732569
601 41 516535006
722 297 796413803
290 343 365298896
277 963 868471797
61 146 625187044
618 937 558042445
883 727 732216297
703 199 199845795
933 464 453611267
252 39 72809535
537 992 6477026
961 299 997729230
82 449 48561139
448 320 196241739
72 798 960750693
911 91 692967726
175 303 459067274
676 996 222673873
723 518 926079736
53 262 562848539
840 383 809465570
703 799 423587952
493 981 198647802
583 951 737885817
978 792 529827148
273 782 207543881
455 306 647838132
40 622 456024488
264 802 603858427
99 494 134767062
201 29 547119764
572 646 482186231
957 107 351730223
228 819 886257992
307 485 884731030
995 173 66616697
425 646 128406970
505 705 900083804
693 412 115390678
380 881 191827479
439 442 252101399
29 700 714640262
500 690 404499030
679 524 8844956
528 771 684264006
955 22 928324360
269 100 683317339
195 203 343120066
409 367 160741511
803 760 865597465
765 936 930829209
51 367 648183444
919 642 60843824
313 952 429719938
778 649 227139833
295 333 623815175
594 817 221307229
262 767 697615661
889 421 580446322
102 849 32348723
824 36 44495652
545 3 564669508
490 422 417133704
619 676 997278070
791 841 81724183
669 985 593416416
389 890 316561119
214 380 952109695
127 298 958597590
829 39 542115989
945 10 631502834
426 670 672986269
320 14 620819443
292 704 70316396
854 195 140341162
710 795 888423296
453 195 372195283
386 180 620368296
152 359 981078860
587 425 709307275
698 578 152416890
914 58 877757218
879 763 221659274
291 374 754747198
430 638 210711680
156 427 747426893
6 272 292937983
485 783 75268836
544 658 337806611
760 175 153301949
879 824 298555492
841 634 904862021
193 989 995184928
330 870 726267787
9 477 193015109
376 386 852060243
527 160 153530411
828 835 930063135
612 732 643385117
904 576 241839479
196 927 838843712
516 900 430381840
242 533 17146638
436 120 461743906
529 277 736380762
437 22 437191602
350 451 978958031
513 429 240995793
742 389 628944267
308 240 244188934
727 248 351388167
757 528 533994308
375 415 547179114
982 739 812163973
962 552 629419901
404 578 964053538
933 514 12448898
701 688 148261421
401 99 327798594
29 314 577420946
881 240 322303768
800 48 974068109
690 820 270968398
511 451 57819815
77 653 33201297
676 538 843348607
756 605 231848217
504 272 646295398
285 638 892731797
481 223 333058671
7 432 432146913
534 386 204839772
355 166 522976362
951 141 298031690
178 216 420689619
91 159 979923639
483 487 877698695
658 918 610591755
968 893 900592094
213 809 951806300
938 864 565197180
511 138 642165453
576 621 912752841
973 213 532176837
932 395 21207711
900 966 552226201
771 570 596534650
597 508 905685542
986 13 881759785
862 979 328642255
701 163 258604164
909 581 262969710
935 373 102329310
13 357 991066817
100 707 890158340
548 917 597920957
521 712 197466387
267 117 354549947
417 790 111856345
864 938 331181923
373 236 860797263
724 681 978836949
558 869 432260276
467 304 385866975
110 396 845354934
852 394 43256763
876 211 240583786
687 45 388121481
666 767 615559118
568 899 360975019
450 267 990483144
823 552 357915408
680 205 61449393
83 166 722331762
971 385 957673001
454 511 412711224
44 642 579174682
635 994 992562464
907 990 40549195
851 397 436340964
746 493 455938377
457 878 883972782
233 145 755436099
931 844 84504363
686 243 151253914
726 95 537162363
817 641 837819014
289 327 408768309
57 923 803659624
495 808 539266005
445 384 258010394
251 255 779332222
275 957 710270012
938 25 520098250
786 141 252380516
575 261 576927897
329 451 137494225
685 809 798198943
241 312 185151082
435 638 79801378
743 146 829702620
676 241 427041264
416 387 540965011
769 379 444712191
247 995 248135412
348 427 933731932
25 620 64985053
100 661 347500055
361 674 390263787
479 970 959727287
425 939 245325079
530 871 644921537
253 631 570633443
546 813 437216691
90 128 755141866
946 525 371027030
475 775 766972193
270 392 531966152
224 111 442147747
615 610 614867813
70 706 448278845
705 294 281434728
655 776 494307974
736 246 105334507
851 14 742059930
231 854 659911093
143 533 109765937
284 94 834475222
353 773 381729314
68 652 32291316
592 807 351689795
99 478 748597914
788 149 966072938
137 998 542121078
415 359 950206232
713 787 641911135
212 208 790716825
501 886 120092832
253 256 9438300
125 12 157305880
934 274 636824902
805 816 48415813
175 608 751970488
461 607 706128800
992 374 604246777
17 261 484634341
140 308 258029581
464 345 568957116
285 329 140309664
94 12 496364157
14 986 211679075
336 627 857697304
191 408 967230544
790 357 267325506
585 417 711463381
513 324 678702781
80 837 720148377
386 185 158732758
20 249 184894600
140 308 253537368
197 528 429176
598 833 294810808
165 298 981544305
843 143 491255614
399 608 785062830
69 305 16189370
194 453 54641703
474 26 933653326
192 227 946314900
496 80 776714418
48 98 173761886
110 396 968468862
238 540 167997815
93 715 689734723
943 948 169250096
944 437 60635380
790 808 663900555
37 835 947645243
327 19 104463369
366 960 267688189
5 164 783392678
306 41 157025990
142 656 452007999
893 357 392041369
130 236 922602113
737 92 200705175
389 488 685027154
842 847 642917405
132 19 84408849
608 413 804857694
522 758 993799005
135 272 671913647
209 146 927182657
592 16 29480020
157 918 948166046
138 451 168974510
185 320 431599422
896 902 462028567
495 417 513011822
329 873 494765844
452 872 366967514
421 473 712434744
711 494 579568623
527 832 344807137
952 505 251069150
79 533 683391034
43 492 653242066
117 940 113813591
802 879 653124758
569 693 582840691
403 221 838312828
899 625 188371818
632 194 794050359
62 940 780034549
167 300 492065826
167 967 460242024
660 143 394925232
552 962 927103406
646 140 241582790
142 116 355097398
344 461 369400747
289 711 998621007
644 440 798715978
904 421 911697733
996 619 574222716
954 174 727986033
387 133 943551302
46 603 273480118
529 277 986394568
377 177 984457060
810 47 610920870
880 381 54581598
676 913 21068055
796 145 869315722
67 177 497953622
252 38 252153974
433 407 758583423
120 579 25197201
846 927 977253507
60 332 701959931
97 801 359937418
397 515 647556104
280 446 901075048
802 915 732570540
321 765 285434605
254 563 791271533
346 45 138500932
415 751 909579839
610 14 330899133
635 703 792648545
229 147 48867994
269 387 101830317
538 241 724321365
993 68 888146927
783 728 474850453
523 193 442459049
995 477 724979473
836 818 851519345
776 874 730118272
708 775 391372977
357 50 232223556
696 269 871240968
288 497 338795274
922 800 779880876
822 573 300461447
182 943 798971939
414 586 759660885
794 959 93296035
938 734 988213799
41 382 783396714
226 574 507326945
385 926 612740850
247 470 383272273
865 675 66809672
867 438 841819457
493 702 117163675
31 88 956682943
50 371 630347595
521 426 730383407
667 156 928563871
236 826 313523853
771 528 175157878
162 611 700826812
438 815 473026430
182 943 941116981
435 430 91841191
841 301 878898825
744 334 740769703
428 409 70625730
112 722 224421508
983 246 396425804
389 464 395221449
650 762 201092016
614 796 598777381
681 328 472462991
603 908 556666994
34 932 78518529
460 556 840377215
888 709 555564706
55 505 925935686
84 87 311980936
465 151 496712909
581 542 743088074
527 378 244749962
269 707 406140120
832 338 698504428
381 178 332226648
281 402 176066168
160 236 234888764
759 349 576071301
303 137 8228529
517 555 717006495
330 624 669758218
309 470 418490676
842 501 851582625
652 541 851549217
893 851 977496240
609 62 26742760
774 410 801111622
767 838 399624779
632 874 222708017
913 103 312331277
34 905 108046089
222 848 328862504
956 427 188157908
556 207 113679196
990 757 732892355
927 788 338840449
25 675 715392526
410 757 401459477
988 632 992771648
94 507 156237039
970 132 248576102
196 210 981812927
311 749 486213287
616 374 19182818
347 445 60210051
824 640 574060894
963 187 594341672
486 318 885038662
704 132 696849118
587 718 143990493
535 482 234469806
25 834 805665223
691 79 284185239
11 501 346060079
835 956 895967456
520 830 816124307
620 131 483162154
210 797 768944293
651 71 540942990
903 906 536698969
186 535 751703938
786 325 42034467
904 465 597336475
393 119 847733833
972 701 672527063
274 401 559045810
250 842 84900825
447 746 149962219
720 443 651862853
912 462 824483432
297 829 132867036
837 489 171517975
64 74 387415914
464 51 495857233
969 598 350581602
462 994 800163521
349 17 427407017
69 973 171756970
781 816 969407756
726 123 488507834
798 446 646118338
163 853 680909333
352 941 385596111
165 97 836596975
286 887 766122492
32 126 124740171
37 828 565554270
69 213 633684191
672 734 839748538
103 313 172713163
687 374 115004593
504 486 170463315
373 408 552839379
27 129 437188930
405 473 630129984
478 891 789528037
510 745 101918801
749 682 153364365
524 991 494097590
627 352 60879663
477 622 975658056
957 81 142372987
378 604 185523156
619 996 739917663
648 686 90066781
964 299 390960785
725 238 743642930
990 907 816865673
682 645 42969180
364 368 271343892
670 425 504626382
728 600 460831710
539 976 365070989
405 904 453907499
222 489 487471760
54 874 45413642
630 517 711975280
569 846 82176557
327 479 474386301
151 171 641260887
368 811 628078607
947 360 720579508
766 108 377035822
168 366 729284081
486 642 983434152
26 964 984706983
743 964 375615773
242 987 60509134
992 155 504564716
701 867 963055548
763 127 916754123
421 508 246196141
459 965 180896481
850 264 208733966
305 20 217440748
637 957 438012553
887 167 3864709
927 959 982740355
569 124 139269998
415 587 224185284
980 4 561111475
293 436 718872079
4 553 810718141
161 438 848471711
424 530 146121469
7 734 520981847
789 619 896929760
363 501 213868267
406 20 105041225
701 474 723269128
900 966 378409940
919 642 662068097
153 606 370955321
784 570 77222955
941 90 399158677
109 578 902100640
16 426 222185282
617 330 130716608
30 738 691063384
301 419 658656243
733 492 455447056
609 62 780288093
498 131 991655387
360 947 637794365
56 36 252582250
271 770 243110770
487 547 839813178
685 86 509642728
156 368 989941682
258 945 744034613
853 891 523088535
232 991 493393150
243 850 254354854
276 598 778225593
520 166 849643159
776 582 660439006
769 818 32866510
35 328 980525424
654 575 141684810
736 287 735766489
350 285 483522015
32 172 551878947
901 330 382535916
441 776 284683004
126 920 384342661
525 630 225241049
442 409 244068262
364 68 620974617
393 136 409330851
375 521 572869036
463 843 381624058
772 130 810791282
228 322 713518308
985 785 145180596
667 239 663132112
518 702 930715093
792 191 963169055
697 802 75366915
533 858 373951606
522 752 561234429
471 356 971317076
708 249 281137734
218 509 375344403
798 231 297486401
175 654 731919208
858 843 507118454
318 919 731756113
397 357 755002879
332 961 81989718
949 772 737834220
160 184 139803773
265 744 486223825
150 914 829451876
152 503 896835476
390 212 283805082
348 889 157374465
966 516 813332155
353 671 823833509
571 651 471502640
49 227 972216458
522 980 856427965
881 454 723253974
123 912 972906597
580 860 320948665
91 95 933145080
129 276 695278114
255 11 278138886
507 439 132998878
352 738 594078365
779 754 589784827
555 501 466822219
322 680 936683563
731 954 819199875
361 856 718158341
758 806 387836237
949 373 868308522
4 249 398437387
549 303 958428983
704 853 922750497
184 826 45424638
299 146 927205374
536 2 796775313
6 753 611640560
124 599 374203232
641 623 199336515
639 595 537417907
947 953 358375193
475 522 621022920
961 332 462381545
399 549 763592670
739 560 247653756
868 748 84830478
547 259 819566184
983 400 246053088
640 243 982100674
294 347 79850641
608 549 10051004
85 676 834387010
174 324 264048740
101 164 867395961
516 55 477107398
928 917 994995435
708 20 859182586
35 797 740561700
592 567 811055636
235 716 52342335
621 433 297077647
270 528 430096505
675 864 250340611
52 469 893930617
64 415 562946959
870 626 211814436
670 359 678303106
349 279 128842470
936 9 148603812
802 489 392090369
300 532 742141045
48 506 101769106
781 192 551618408
843 201 578544555
954 273 412998357
727 404 18483985
503 288 980741364
1000 803 340567467
756 94 147542050
176 354 145839681
952 294 931486325
410 270 906795564
794 595 724266887
988 814 249150066
350 873 556148831
921 659 202575210
844 487 676704965
939 359 31551966
583 490 496057024
216 887 272220719
823 684 209877897
372 613 527096572
533 660 121173548
905 355 801531837
926 385 519446596
431 171 985103301
678 30 953447937
960 981 483237919
913 241 611781782
232 978 776895583
465 317 351679585
155 336 629385776
148 737 78072345
638 174 666601629
900 176 378977787
721 799 182352527
268 78 272832906
178 531 785358203
470 219 854452709
880 190 135996716
492 61 558556967
791 301 700028219
19 711 605586871
886 226 329558468
29 123 83485667
204 275 537970509
720 402 554305385
729 7 178460256
157 884 941888893
136 753 313848926
718 16 900464771
47 940 968912662
372 195 850015137
392 757 800704805
616 687 279512990
738 175 350679626
355 83 120589309
98 870 458468191
799 430 614254157
948 666 685309264
407 461 284027191
311 965 700737900
155 235 240738907
316 250 482827115
552 31 843774832
945 158 174163072
178 796 240771387
225 89 954765765
847 735 764296721
813 200 961837073
71 819 536281751
959 788 732366330
513 912 386472343
827 319 423601050
490 822 137706485
261 245 538301619
280 651 235411611
563 826 618170379
446 72 174623252
435 731 157421525
600 773 355202848
844 360 359334880
16 512 394805212
968 893 626034606
918 601 447409496
472 108 314001148
834 460 388917989
966 354 321055532
394 882 995332349
464 742 371796746
622 266 932055037
709 428 418441882
924 510 570946575
95 123 25956866
610 394 989773178
930 530 889428827
945 358 381831608
204 107 893792462
668 67 812314826
76 712 499194439
435 635 944255529
732 985 999433647
688 972 166846675
384 103 713962741
758 296 898720116
178 233 476609073
405 171 306325990
341 267 865547263
686 243 791072444
67 668 80626607
551 47 363766174
418 172 246671567
208 447 51683284
918 192 957323373
673 551 661176459
800 901 99946709
37 811 343511366
631 75 498581113
495 13 740184904
877 364 147432397
787 120 765336691
818 530 611287968
647 420 237787340
938 556 482490895
769 818 135877870
929 204 449398945
695 96 892994402
848 115 924796082
391 251 766352732
233 178 655342494
337 67 178620517
216 233 567082014
456 588 701765258
257 832 838730602
748 202 247546935
100 650 195383889
55 516 127048733
543 283 644939393
107 232 349837087
816 192 74916600
96 589 476008237
378 470 809691054
252 111 725884961
262 928 110508741
911 861 633161972
975 644 466763250
238 6 323095296
548 868 304455052
150 668 762854702
458 677 207671335
708 475 856407411
785 727 515857586
913 347 167965830
259 170 509140323
665 861 672355996
736 246 925020253
147 584 454193014
727 920 582705002
678 716 861625163
296 973 299984115
605 702 124336135
241 913 613720866
198 496 351336336
411 15 524704638
653 229 310837690
478 401 421061594
360 487 190941007
328 35 59472374
21 1 352429431
561 296 227438022
362 875 771334009
738 28 572304955
976 614 649887192
990 757 149355058
495 585 738128277
798 217 603180441
534 182 668014064
125 284 715319281
953 244 137744439
189 384 914345113
465 407 195466901
524 107 977560180
860 795 475871206
370 127 102157675
861 617 968541033
857 381 716493714
707 762 146974724
568 579 760796057
42 593 502067285
746 423 995915709
328 158 5118109
359 562 435930991
74 521 826365984
141 786 363072460
87 203 283732441
270 23 65013432
721 242 545891601
114 159 992332829
721 429 481937213
430 513 438824471
233 216 149958343
62 78 378926305
92 222 324563847
286 145 528717819
438 105 230487190
526 556 938961006
1 601 465435227
943 150 894480883
659 35 593593425
11 431 92314192
660 95 418230453
59 263 139858224
205 390 471930387
81 133 453450626
586 825 911247891
991 107 877324097
165 745 493371058
622 868 102524720
766 80 882563160
450 525 796366468
395 85 52018830
239 811 656002126
495 397 351592238
750 265 741394183
338 236 965558623
772 629 769765545
849 590 774666481
207 834 299874925
744 838 857825961
695 817 668143159
320 515 780273089
770 113 758904501
234 936 48926895
766 848 135537207
246 287 419168881
622 868 973031055
303 554 442874573
202 53 591979929
412 60 860047386
478 704 534663637
197 410 568605137
279 34 391114727
496 218 77360563
324 925 929771613
139 499 455641708
178 542 553856121
931 844 972420543
46 855 219501791
930 530 907660975
676 558 56020098
165 710 25006270
418 829 591665140
266 179 452628410
61 230 703684474
379 685 568760532
853 388 159693246
484 411 915763408
169 569 790627722
660 143 827700648
722 111 125217505
429 199 507494242
47 109 926944728
8 491 901519502
992 352 519454915
958 459 356192549
171 344 759120237
275 637 999053973
913 444 568991175
406 685 457732064
330 665 524042228
60 237 763082724
162 427 534335136
490 706 750387568
649 154 953844014
394 13 452434731
68 896 159195741
144 557 654820957
265 58 487856534
453 260 629025494
335 206 529591879
477 398 648825076
299 412 85120286
510 271 637098575
516 189 321135086
131 207 57337556
568 674 533503682
59 336 899210410
655 217 430516995
559 316 354555341
663 594 886058997
606 307 698036549
420 647 881181399
979 511 528450593
718 426 117784918
159 624 912572780
362 188 446787492
956 667 244279224
374 716 663189820
754 880 984796091
499 316 411858870
202 917 230937020
369 949 777126728
192 977 682407019
297 33 196054268
157 306 564764042
550 225 97214992
509 697 727321829
209 412 772262164
206 922 332701762
860 293 9836627
871 769 825991256
798 571 781386764
340 231 350339670
788 124 190865325
421 317 31148974
685 530 619380097
775 406 382884174
177 180 92129672
916 600 770508917
156 993 127873842
290 191 472205200
868 65 465262825
646 471 815364242
393 371 611004878
116 791 771768566
839 378 473608796
188 902 77035258
741 775 198025197
523 131 115987091
557 792 854208195
423 168 450088966
336 777 219036978
480 199 410527155
674 353 322560775
964 733 366218266
92 218 946349389
953 967 421609352
381 101 348209265
568 293 521982128
365 821 831283864
4 475 975206956
395 520 970605190
710 403 133044171
47 109 329696850
984 196 259996744
427 37 665116326
647 373 402626540
547 487 281121494
95 533 169116822
128 761 729783597
41 730 899177683
223 339 875372816
134 10 245900078
801 648 727290877
225 458 294948064
214 862 368134313
897 935 778121589
555 363 71163346
3 840 972567380
619 892 381523654
689 596 508275803
282 278 667737711
828 971 290890505
647 369 517415338
927 124 515254359
428 409 649845638
232 557 731052717
798 186 609917376
309 527 943819080
889 433 342413409
873 350 738378164
242 462 395053363
788 813 540396381
502 44 353253115
176 331 894769552
45 856 888056899
797 287 862844072
390 322 865964979
513 994 455697239
699 553 404496493
493 723 652179185
87 453 963695508
682 281 606139522
917 948 783412465
155 716 314345600
165 298 780941207
43 743 962138038
179 885 708578037
447 493 664943366
331 187 437352382
868 266 478823928
588 458 183558125
483 840 501804940
327 31 69272846
857 779 183714674
319 706 199122292
400 650 201122370
681 328 896050019
450 267 514635431
831 632 845197674
403 860 899939129
748 53 625456312
642 689 50510676
949 897 273818745
954 638 139457543
453 84 670092129
891 161 662312198
113 411 185630188
508 162 976513669
514 649 794271457
422 197 919485916
302 458 197119665
44 540 395094520
439 284 404994178
985 404 660633727
470 765 372329037
266 398 84684830
855 908 377183866
776 613 171029247
617 114 579083428
727 920 380531930
459 749 245630138
427 835 995321638
12 756 518789375
607 889 182889298
58 750 462144085
473 597 784439448
390 819 630465002
602 618 149194254
619 85 629082053
39 418 656007385
712 592 105067302
867 292 175564809
795 42 396152962
173 342 335554794
804 368 648262961
472 108 305413894
5 315 827848597
243 763 969578723
683 74 992060316
935 949 757981240
399 413 245477789
588 458 779860253
169 124 742201509
567 190 193343538
407 344 793409065
977 104 212250271
167 178 137399320
868 948 54566258
994 635 750309478
705 66 231496422
825 866 274737522
573 729 68923189
519 671 961376970
698 612 378178957
185 657 697204809
915 850 778859678
946 551 621597702
702 125 473066624
420 160 678721025
272 695 741628802
326 567 438108193
351 841 782375503
525 450 569217922
916 783 847231019
624 700 238150095
166 83 815819783
3 566 260197233
948 666 886211015
373 647 619450277
123 463 762271815
466 787 199453136
428 51 115773299
580 411 114792483
931 953 867278382
380 636 414808413
265 895 623552111
22 555 321418925
342 458 328977024
297 989 254873017
509 766 395136797
511 256 760756074
401 132 167147711
102 1 695331800
122 910 317605327
225 89 773684831
782 324 429200553
63 310 89599197
677 898 285481960
120 795 670382515
513 430 381104795
875 855 227260861
756 493 325051452
828 811 100014626
786 7 842242090
290 107 547940771
140 152 593831427
370 770 896637789
115 719 338560967
316 268 117227225
209 639 279202244
722 121 684447224
517 555 890914902
997 487 393348
658 41 762300805
149 764 412645975
815 292 209885682
892 444 589461069
558 876 828036198
190 592 389543362
7 675 250413175
402 311 505584388
75 256 733979358
966 705 243790749
133 650 755191366
286 953 78928255
239 427 583731971
883 609 866361121
516 187 223877875
283 372 960559794
967 947 313127119
343 93 924686112
88 942 158910995
146 688 674933366
38 920 801317347
829 669 229422445
615 852 27346088
888 442 595783361
194 54 369072299
869 892 180446511
499 946 221853965
121 297 338943585
201 29 188757662
740 851 933587740
623 663 243596725
605 434 725847720
713 717 933419337
509 92 603448273
791 116 99350505
835 971 890081957
661 358 893654241
323 498 548537112
339 481 394040686
110 818 25608941
501 437 535729646
913 789 575594090
526 523 260531167
208 518 895101876
158 134 515200885
865 734 437573317
878 529 620600593
145 167 589016981
10 707 850789863
901 958 732653150
698 252 929769302
895 534 775631697
172 669 57562863
981 493 672215208
644 696 282812961
694 435 387169511
491 349 7783977
563 772 562013457
896 652 851509043
498 414 34856510
386 714 718212461
173 63 47158915
433 576 377587915
563 949 193249228
906 774 562062598
233 754 735429694
356 939 405469615
604 591 431647697
220 457 511095008
372 655 321568303
34 211 565629337
973 758 259250478
918 102 308030789
80 218 652338072
677 885 933494828
360 244 113387668
382 805 410110590
353 82 434411931
388 867 980980137
892 313 580196518
83 932 68030532
988 814 348034141
644 387 203620478
762 416 501259676
488 566 887290556
761 28 97971679
893 394 436698199
751 64 641047680
509 848 961309390
686 801 327264220
819 186 350938598
163 812 331796253
549 998 880976303
491 215 808653239
787 568 137656038
692 990 144378252
375 683 97611682
999 855 628089411
563 897 440160855
838 744 217056626
481 724 511630579
560 664 337768044
401 478 629247740
289 962 883074473
889 618 702177380
31 88 521099981
550 456 576099244
653 133 700506291
670 74 199102545
577 254 597924381
901 749 427665476
715 191 847107095
440 661 141778601
355 520 671313073
98 922 40429372
715 183 371242071
242 513 243161240
953 844 551690127
673 341 34505427
5 909 34271906
4 758 328478421
708 475 197001843
548 622 30978914
903 906 469754031
669 32 304437375
15 293 752826202
780 921 49486622
433 465 354476246
545 566 648997846
81 144 273979031
565 781 126685718
771 692 761442531
431 151 58362608
553 31 347383202
977 565 637653532
548 677 143542526
70 25 561744848
339 500 944023735
230 388 162871148
837 198 986180758
839 321 651828198
785 612 127158636
935 191 463494055
18 752 217572280
139 735 430200731
815 163 404209618
385 811 676498427
915 824 440894944
344 621 51640656
969 21 245754964
4 406 473624847
5 381 654353256
237 961 537424083
208 518 420650087
770 271 11031188
522 31 652496793
38 669 233640747
821 713 36516829
950 755 484683414
736 481 60267855
639 964 682711187
24 715 725979299
778 51 27790735
195 655 365698724
679 107 521861286
354 963 485894185
515 610 828839558
498 523 367514555
302 65 265809319
811 385 140272465
936 247 106859729
884 849 146555745
333 322 840011110
926 877 60363919
940 845 944940986
593 484 420633058
521 683 382184629
237 813 788092342
925 635 564899174
419 875 474016768
485 643 372415989
506 98 618919851
789 538 4520649
684 699 116187401
325 7 171443264
156 896 36146301
631 979 362153482
616 678 212122952
181 768 922185981
141 827 643963099
135 96 75703666
694 638 802044332
800 48 200777202
930 685 594054614
574 517 936467387
304 375 29309865
621 602 191545047
138 452 721050145
113 580 15044238
686 801 615745480
947 547 509583911
114 330 27075621
965 958 2859360
659 984 965514191
831 632 24094350
148 108 903453035
74 718 571113031
265 744 583970872
461 57 66675264
945 258 488599001
883 810 842179864
434 888 308030284
294 241 278159364
441 874 815470786
323 526 826297661
317 889 36380201
946 139 229100279
701 815 54075149
862 214 995371797
636 881 387890775
407 317 400205365
958 402 741912968
154 389 879997358
406 809 600959721
244 840 461472798
833 730 704612453
215 399 149479338
591 321 190560610
284 12 387230775
607 317 597020961
551 609 109807589
830 469 942476747
574 57 411294222
162 971 680325222
271 221 903967786
629 577 406068335
727 793 298698695
384 313 424881484
310 234 801262090
608 739 831169317
292 132 925861611
770 113 357305887
406 758 141792977
885 677 5476747
955 559 145091392
409 933 886085808
299 693 416735607
578 883 876779094
795 271 925822206
617 91 701751719
562 572 522287335
576 889 850844592
433 431 379050669
372 87 737020486
118 153 410051536
28 760 477493746
875 855 264868161
572 140 90130762
451 731 628851663
177 181 750841834
788 959 574886646
894 681 900279937
863 736 466036457
922 901 188118019
729 583 184219481
443 720 55712409
815 26 458894264
186 854 735231908
570 270 500577453
503 240 905882527
595 60 699723934
894 945 782830324
288 253 154421990
355 312 206922761
76 74 446681267
651 333 498651776
35 780 977094657
139 268 578142052
907 490 401732423
86 561 196746464
648 824 753050200
768 668 440896470
324 242 629761903
984 200 220412669
105 815 660715604
81 978 537339329
671 916 810758126
660 463 665738858
272 318 307661965
268 955 526894145
523 620 714961850
432 729 737087077
939 503 88113308
165 686 700540659
240 253 859273138
18 806 85332661
650 975 166618707
592 683 379044863
136 663 577635077
764 500 918955739
445 900 279033768
134 662 932443765
772 832 792799493
596 468 725770660
654 982 657521422
578 248 928510246
634 142 811801274
458 225 599948649
398 342 946816931
937 421 193618617
839 765 662666177
921 149 214709073
668 337 244085444
682 901 461952293
506 950 135286003
758 475 479475740
791 999 229865033
410 392 557206513
820 780 200408318
111 33 566186428
261 575 789563750
734 827 886948772
392 23 430482274
706 325 813507524
859 486 283215177
162 602 357858898
858 691 545706109
498 586 243768750
786 827 321155824
874 988 484023243
136 740 431343119
327 19 751672479
792 290 489880337
413 8 197416684
13 968 154586839
315 300 311823733
974 387 509908365
806 18 475951841
625 365 8790913
887 539 998757212
10 440 730620264
313 966 291365365
742 997 131837565
590 472 854677901
773 346 275861877
78 673 495017445
401 853 301536769
575 759 106628279
212 981 774271309
86 213 771854368
534 181 502422214
971 877 372806033
338 130 835323958
314 506 819949189
785 883 142070286
469 996 683107733
11 151 40162432
65 548 196892600
135 808 743251118
2 220 848079456
245 279 305693049
866 112 254046864
358 650 501721534
367 778 36772227
467 512 939686429
982 654 508412135
689 589 974542690
859 129 645696868
626 335 277487558
442 439 456183214
297 224 165058369
972 43 249373954
255 11 991106757
24 935 117882592
809 708 608733242
230 733 25887882
483 488 950526798
740 495 227912196
657 73 770900161
33 252 718797580
525 673 513552784
791 875 179082463
97 801 21987089
608 549 566990557
747 814 153756634
583 822 434364387
108 49 894615129
268 117 642619897
332 169 664355460
449 45 281822931
417 397 519378187
824 648 68739147
162 421 600705722
307 485 951781893
947 967 245136665
645 281 879893116
471 64 155241971
217 84 834719642
525 268 653448922
369 191 688535512
148 115 175186883
564 744 765878145
741 69 520647280
613 453 846263530
979 380 253459454
383 545 605399960
428 778 813877224
40 477 453710290
973 530 366767400
364 926 544544245
183 24 43680525
979 873 249027989
482 798 928964075
343 191 772560387
273 703 614055857
797 35 608603507
807 76 435986223
647 290 898680004
579 466 758804137
556 586 222287552
349 608 109671670
830 312 482254186
856 519 88439932
735 630 556454759
897 257 986971768
538 103 551473116
733 230 614316609
528 951 748743080
889 602 7657251
3 967 388830366
928 262 672038023
702 723 524882988
671 773 954658903
203 340 636249290
647 369 267477940
345 409 795020524
540 859 642750999
664 608 234801998
288 572 446459522
699 31 150740556
428 888 611902177
757 784 992432864
857 779 488208204
335 206 451210611
164 326 925695287
461 407 950098985
677 40 835834039
760 1000 76466735
705 505 497511272
632 441 409433038
565 455 725935781
947 383 195417989
981 746 7643080
367 778 951312505
755 617 101491937
235 59 264936168
246 258 25782710
480 513 338147439
291 687 977428811
549 575 319609184
827 907 562320953
45 118 825051540
486 318 408500872
924 370 465005599
898 302 995135708
278 292 368232012
942 289 450687863
564 182 632838977
347 189 504712695
408 93 832679894
412 209 108518395
157 884 2194006
225 458 939832042
320 851 706360404
420 254 163768763
782 694 896910992
494 479 1621644
808 393 754576528
132 934 209498833
938 25 214506225
582 54 517824233
837 697 359557945
866 172 960546501
114 476 682939316
6 119 537778193
263 941 942041287
778 605 663012884
239 37 743588493
70 865 517886199
751 64 346301868
249 475 903847932
217 854 14776990
15 579 604562448
713 916 952918173
536 331 634235666
686 745 770206754
73 377 93260858
416 650 171666720
63 477 493526376
603 188 130292141
489 122 635307183
968 585 609808646
371 740 57463913
880 857 692235047
482 295 451237212
211 830 247669447
871 424 298263311
412 169 825167951
487 947 966049620
765 247 491387533
312 52 818956256
773 307 770128098
531 5 130328336
554 137 282001607
425 426 994391275
219 995 849163442
23 903 698203930
67 265 847666492
59 155 616549202
595 639 387479971
908 628 276054560
109 940 633298566
106 298 831227404
542 857 371880922
133 77 690518111
964 299 672392451
717 361 787732657
998 654 233917804
712 467 272596884
169 209 548878797
117 499 877530579
891 274 162038190
320 657 420294162
573 692 898244229
903 422 591841073
991 929 695133131
430 994 485009660
326 779 37926607
56 697 771036092
178 531 828495463
258 894 340439787
432 672 868823864
902 362 275714013
497 308 331173051
745 106 493295404
967 286 300626354
767 943 711726196
730 969 269740813
333 482 414285230
923 391 539221523
861 476 898294968
725 44 411912256
760 738 32059739
377 714 912913848
793 551 957917277
433 405 355802891
66 176 458133555
2 55 279091150
801 165 327108084
538 189 594279757
863 894 397852083
759 8 440058889
714 615 356109429
974 929 471560801
927 794 490039007
264 36 813206207
325 141 575710167
611 348 61265395
536 582 557969362
222 198 461747517
882 448 854225985
635 480 294549548
28 263 819859801
192 884 375470538
172 224 611989498
349 399 814925818
461 251 76297516
53 334 749706041
641 136 35114585
408 290 845515405
334 534 805726062
953 483 284881531
541 46 438425870
630 944 744616429
102 565 442327101
117 551 96521022
143 726 326298442
626 335 598721215
334 750 729314957
988 441 346821733
557 679 904548242
308 359 130890192
753 504 330137456
138 329 214355123
708 213 873121441
4 806 20534470
367 890 57029768
256 214 669394514
412 61 506415812
628 116 950074701
566 931 529399109
464 367 905433930
920 698 209990163
462 858 618544895
532 216 643225766
221 924 76812886
14 448 513139943
362 351 473465531
965 633 922418893
453 747 609915596
803 263 283567708
211 932 652951604
922 800 385453941
552 327 455271792
504 663 780321355
404 248 917695229
287 223 995799191
799 480 496016090
895 534 514161761
599 984 479917287
872 873 586273488
872 329 381552117
532 286 466386460
231 446 730985787
248 883 106433339
239 926 733015977
294 789 818964720
192 544 975397322
551 946 746076850
816 544 520939961
334 564 376553674
990 270 882231376
342 550 132829633
873 782 361355191
693 412 611721100
713 568 423406607
561 708 62266975