1000 3000 1
371 186 518495171
272 401 108256226
551 506 571634169
425 604 488632736
740 875 326162425
614 608 257686454
609 970 371079829
78 208 696442591
38 662 952880747
72 64 825265129
768 251 859161916
835 428 871483269
691 224 132556138
910 631 737199194
681 10 477562537
948 254 246043534
828 864 490660641
714 147 976837600
916 624 261235962
265 201 890435726
317 374 640402775
451 895 646216429
787 859 719510199
844 589 350687824
81 583 497174599
880 212 650039468
281 488 770617527
981 518 614712687
962 207 924532172
574 527 894242487
946 833 651438172
957 116 976714805
813 890 482811215
599 851 311834423
932 742 316632263
362 564 192552327
713 642 730773414
133 865 716108261
242 831 118426801
636 17 982705222
761 841 512098485
704 423 405227732
419 165 362708109
273 500 548775950
408 757 871755275
447 648 109606005
243 830 589652572
815 64 820236026
311 565 554734294
619 286 924306797
470 634 594489016
334 48 856993325
931 321 130840121
340 399 709054995
789 600 247619879
394 900 259257063
557 147 589917161
201 631 126290565
151 357 872486881
468 688 207162459
144 576 877331877
495 686 812669497
690 585 546525088
221 713 37524005
786 608 191154104
835 787 739710228
919 196 969026125
15 911 927141643
890 541 909121891
50 448 918459606
754 526 432925018
204 962 548132291
999 205 468769055
20 66 77308198
771 364 815705363
813 236 928344551
284 43 713930106
595 634 773424142
192 914 655721047
166 437 913720787
864 413 185603999
784 986 467738727
495 585 453986814
67 888 432298101
231 349 532546934
268 674 961417791
367 92 307431458
511 241 387770517
402 435 381855232
102 395 486974960
905 600 635161408
358 721 223567639
83 766 424662747
446 979 708481937
208 916 314993733
189 187 919066659
305 766 102596451
453 166 816009207
306 293 212336850
735 384 860684576
330 681 913908908
819 272 807227146
245 978 246301606
479 568 341376238
305 762 983073702
436 451 390582723
918 541 41859896
454 657 561009400
405 905 563126727
271 49 398507085
639 376 775087411
745 345 537598145
78 314 56416856
480 983 890764031
606 110 839540988
458 828 465577782
655 286 830416598
400 257 631271299
668 335 551174033
131 933 75098225
519 460 667069688
461 702 846839517
874 670 734594517
503 654 26728960
411 732 515619582
82 457 262406442
307 699 439346534
169 320 591566084
369 812 96848978
51 490 404233788
85 789 337596683
742 249 351434974
348 577 993196667
917 717 645523499
933 944 972196284
998 188 930342166
110 456 550788976
574 132 985335155
487 751 580626268
785 926 669159236
112 629 505051397
597 82 951851412
75 995 242282924
988 502 413038189
815 633 47172740
179 382 181132438
355 537 191654354
958 720 978569353
362 473 899605792
274 714 962998333
61 785 31803549
134 352 772995085
643 2 992226062
568 633 164285603
159 295 829749183
454 127 181003362
527 142 355095412
730 334 532278300
886 638 586977180
543 65 583855850
834 851 85463073
615 151 51007139
19 71 513078071
475 728 589506717
347 519 858408689
221 42 332439374
623 370 240126078
143 716 557620535
67 200 480911959
959 77 81510451
791 269 735480288
134 924 869610216
823 367 390138461
182 591 455144823
315 753 740136294
105 973 672485094
379 511 422568956
165 795 89883739
828 368 247280368
174 882 290950376
782 869 332801096
90 48 868577172
125 341 663097204
831 248 155402502
41 330 840585907
195 248 208124027
703 218 458423151
232 459 36749262
25 890 496688573
389 986 444123266
984 5 909842393
966 278 402304970
49 737 669173864
586 930 938134598
823 42 996897512
516 272 580814182
246 854 91405335
132 383 914779760
580 655 489727744
808 440 251330386
996 560 266639108
174 653 88429767
558 943 682487448
600 101 90020604
925 805 158852416
341 76 107158129
151 471 252414252
546 620 876807679
389 570 273520404
417 922 543156246
815 236 816256853
142 997 217981584
924 629 636686609
256 278 151672355
486 659 601609755
195 862 813860277
332 321 966781800
865 36 263377914
244 140 491659041
894 596 335967781
656 896 260647596
925 586 536649696
874 981 267529716
501 987 186598535
644 394 311521719
871 933 15063426
14 925 668701317
459 378 420655637
877 714 749069109
551 271 113258800
704 64 980621355
725 171 979028900
466 570 685032304
430 618 91680628
839 551 500856209
211 579 23247602
791 879 446760281
817 549 714761391
789 73 417895690
304 885 598505688
27 816 682780892
108 337 565050126
248 113 489240211
769 313 202747155
351 619 479673701
857 47 595028791
745 233 584753202
260 139 311882063
141 693 935971108
933 284 715721845
469 474 49933878
515 883 253373956
697 46 733247958
921 292 567728909
14 966 506124968
47 486 274396398
728 86 977381167
950 324 962498059
315 479 633636237
283 966 187731727
312 619 4439579
827 577 822460828
788 739 407600406
286 798 971350391
237 429 967481817
121 209 796449862
840 909 425690630
377 629 124933300
449 532 323982966
449 547 138391335
199 560 104266351
473 968 916491543
756 371 956007214
948 711 906029974
370 911 165226120
217 259 142055107
940 722 21801659
216 885 97769722
980 458 409398494
659 530 215039889
782 294 941456784
240 702 729965447
765 936 150944411
527 190 258691457
699 574 476861341
631 551 33536853
703 130 651530636
359 132 649081292
991 538 353814356
670 923 683758734
402 566 74107520
480 216 355958980
35 801 91502889
534 755 498228596
314 415 39941352
323 94 789466671
190 459 48344466
674 795 446893034
330 793 813131818
684 221 743750238
81 995 719036152
985 757 690901082
623 716 144762091
891 754 872932428
381 544 164423653
285 269 835579238
819 784 289116902
574 122 975067208
948 21 626154252
852 155 12181687
554 709 466763647
297 604 74513937
58 763 447582302
473 475 665357080
259 109 125445787
41 387 669863510
785 801 401454572
358 587 708786800
279 953 598984135
786 815 483304161
97 69 373422932
518 1 720095469
494 853 235690858
305 616 62675451
105 827 799002647
935 680 180020402
589 67 254823047
751 770 556550172
859 59 242531047
420 743 649018044
443 559 351927095
353 722 965627013
928 875 830575930
193 194 457108645
950 494 114834855
504 564 579498823
670 961 331121868
357 8 575995586
227 672 111639840
100 685 38390293
293 119 913819333
618 795 940111096
969 901 614551005
345 973 583673593
163 83 973455986
292 835 92692963
88 246 773909178
858 873 245796683
797 677 26067726
559 916 23889996
510 725 513620829
809 811 525401988
577 255 258828041
671 861 510157797
194 598 364524198
332 229 839621068
886 712 333201390
168 887 726153763
873 886 988344250
268 13 315732744
11 44 167795100
244 38 642363357
875 746 422608912
740 544 714188527
506 623 798850092
597 276 447178420
119 97 730980498
603 74 940826918
574 337 45187752
421 687 536396448
202 55 733415794
879 968 340364365
931 540 423656804
688 727 522285233
680 343 62409605
575 204 84688308
892 433 736204709
160 423 805353894
626 139 248653386
300 710 792501696
606 584 269576454
297 961 498405440
619 751 100379138
179 676 275773146
488 584 480601355
49 808 827782075
249 326 427119484
314 721 885046166
686 24 583539549
670 945 315603103
15 387 286559516
688 162 504053483
150 766 530256911
479 584 380489846
858 537 34340637
789 357 749630301
685 17 235023141
256 695 200761881
419 869 866749292
128 951 712851575
273 760 560164786
963 58 665361816
165 828 967961188
371 71 290597112
186 34 155047690
684 307 537899475
529 584 272340671
661 389 467078566
811 737 829549579
990 842 215143225
996 386 620227131
135 703 150918443
820 384 697292457
869 997 203922403
49 68 965067288
190 155 917248803
901 613 316538113
418 829 904350722
916 368 181608037
185 208 502929828
1 888 192942380
684 33 753286628
202 788 165267811
442 188 126156315
785 984 927236788
932 460 241169276
904 276 263883879
114 733 424120403
917 352 491412798
738 149 96081989
491 29 753017381
796 470 559095133
932 102 568622631
692 39 799816714
649 658 864491787
788 234 333283443
747 189 896602904
235 757 874600506
254 156 222690929
490 187 258101274
736 425 449590234
66 957 854028136
81 892 704363560
680 802 26276261
454 505 364873417
138 35 918888932
49 98 981201114
408 921 274832228
314 934 375271491
398 959 3525176
766 727 546878517
752 649 845731097
815 439 220754969
414 492 35531577
414 223 142065147
490 554 873715910
255 444 232712890
986 987 178771809
660 179 774598183
108 500 178995532
932 267 250835102
57 920 761776633
388 341 576947391
990 178 403424351
557 811 499575712
905 14 433906261
189 778 241669663
185 410 592868728
516 972 908036825
854 69 301655365
648 982 427664307
632 877 131067001
734 687 366799637
647 259 334550051
398 551 233105134
110 343 288791670
780 259 702270162
987 387 941088937
231 264 30488990
8 943 335157245
162 620 385026160
219 514 91566553
903 478 400593239
242 711 72882609
867 493 308686718
272 550 434564834
68 831 658464315
254 749 175852060
891 342 88857471
495 390 32052594
202 666 505257713
435 600 828114056
96 227 229254272
299 421 780192310
409 82 807320018
94 122 998061312
989 349 561231396
37 481 432938358
747 764 415700787
755 671 54626280
557 229 301456471
261 924 950875912
644 832 751407814
206 931 663115673
947 977 106525035
601 528 231886872
697 106 603141736
798 396 308652335
847 898 446670034
459 204 26398989
773 200 43178575
12 473 428071960
413 298 75931066
666 783 705414295
806 490 220259384
923 556 322424150
955 893 191117802
712 908 323570693
924 193 868966132
152 254 567074178
956 763 968850060
405 272 623393235
865 34 423080734
591 614 170461255
886 765 467962592
3 778 279545712
912 342 470208852
866 688 916691988
97 675 156639732
94 319 788816031
838 375 8176116
278 642 411085281
649 420 251105136
130 492 501574947
599 716 888689181
286 941 628547316
607 967 690607633
96 73 804118659
934 234 849015896
411 758 90045902
273 982 875603792
474 103 668000763
62 147 569271714
869 822 176274808
148 426 460234812
497 788 667873424
278 44 370883598
319 203 524032261
317 299 667743705
96 748 908243445
422 463 210631868
420 570 613194760
96 228 9195646
242 941 833518860
588 725 249912464
851 660 579750475
748 426 496059935
552 157 224637588
712 884 957778830
820 909 977239399
89 32 200584488
11 787 962450340
79 742 384261834
462 920 974730540
76 244 6108717
528 942 27780380
593 709 250814061
833 703 3893042
443 913 100216654
418 374 749495765
441 26 384670809
201 166 70291665
519 986 232153450
300 352 630777289
728 637 103330202
731 611 261482187
766 440 717530983
3 173 972678155
360 40 340102897
588 360 49429304
720 686 311080178
622 120 186748125
230 266 283048513
141 258 157860969
403 986 153894186
74 131 110993206
655 641 952881418
829 366 40303269
352 420 867023448
963 495 746343113
907 723 959860414
615 503 305639623
876 354 819038204
642 728 699516930
549 382 448947709
222 549 684769698
940 270 822887461
879 148 382487925
820 763 543482030
27 441 380118491
819 716 378951376
200 10 101233030
955 308 923125949
825 418 934531935
445 262 759523604
222 513 451823728
921 952 494332486
504 764 898330654
580 286 779262072
3 255 431048506
837 823 455979245
377 518 870919539
29 890 558243871
493 279 732590746
302 152 124275869
239 218 719182246
917 133 347326694
756 639 718646007
57 172 241227047
568 810 990187066
4 261 264420930
690 953 287318541
709 506 138468800
466 696 321762207
327 544 370775255
43 59 336063374
656 243 448282857
946 719 953227671
405 685 155917091
46 547 50713006
446 49 684566176
470 866 993145550
311 968 883290525
826 947 37519603
237 964 687214686
911 849 711614686
878 7 983271514
294 70 933156827
240 601 970877947
368 666 423082171
685 774 376901454
12 261 183420892
308 567 439600099
767 311 888036528
198 289 606151433
332 61 780598990
946 177 367833870
763 646 853233341
963 68 966259683
887 432 801541622
484 489 372904187
638 32 339210723
254 832 858649885
435 980 532835494
682 169 976628107
898 273 722243349
188 273 386037502
919 992 896479925
34 423 160035645
481 544 681390457
305 126 779931161
507 413 984835796
458 193 925924562
765 770 932475657
548 876 478792628
385 225 961769590
273 161 111784944
386 617 476391412
529 335 155326092
586 372 51835282
172 332 625150799
363 473 379145839
87 252 88323780
725 149 561729146
165 726 757401919
900 108 492767665
358 478 922514716
462 217 46732622
869 720 669400380
634 329 603976258
141 88 411716328
300 187 644894065
540 387 586569666
245 490 819197852
101 11 293288359
86 534 570748900
904 476 735651854
848 556 769424568
544 103 806970419
672 467 505112316
552 179 404572680
448 367 668560233
913 486 396519343
391 97 424242167
977 534 792570072
104 662 455193798
107 283 604477248
90 340 733967081
523 842 733710138
269 805 618829235
597 798 518940166
641 929 922478334
105 828 488107487
394 81 808302196
488 578 105972321
828 332 60382567
122 51 640435125
849 630 652204509
124 626 699976013
413 138 213576665
195 127 868237914
183 378 738365479
682 596 813293904
14 726 745184039
429 202 901978140
191 867 789764034
730 18 973601140
760 624 598283320
597 514 137716892
653 297 718052034
59 145 250296123
59 231 944364454
690 439 535387535
889 349 497740594
935 791 325567107
260 203 7710548
322 350 942655123
965 844 549704453
12 768 860568905
856 374 647897667
157 96 831574665
303 4 400014074
260 916 225866448
272 465 263108668
223 418 507246841
571 405 830918426
177 614 306839438
459 287 991999378
349 766 383716954
150 381 127860192
896 81 362577202
937 938 339832616
977 410 595341622
599 293 45206627
99 106 594426454
494 267 680729205
614 10 88445219
262 842 696383985
726 205 260087424
868 999 609905773
279 565 688009530
941 914 292223333
990 765 418976004
352 740 628615277
590 479 468736650
82 577 403358041
32 237 132118340
338 89 183891348
958 723 437348868
166 240 910511808
701 989 314312902
940 331 689283080
361 862 155992100
23 348 88853182
320 698 502788714
643 859 416087429
57 138 113932877
966 189 774555572
783 396 97632211
495 267 652188027
812 260 506089570
987 160 325893530
503 936 841777903
594 756 34260013
815 14 898565804
97 712 542956766
834 807 50740966
578 933 25571667
521 694 771965956
996 158 846344460
204 74 34378133
134 546 116974063
487 649 307334362
792 924 823891272
178 326 333695515
516 988 403239306
503 383 401699175
972 108 342448837
993 53 892797340
352 757 781768175
334 748 302492429
433 14 315155029
594 803 65911955
670 388 502921822
104 778 306171377
985 694 444690315
804 328 70625727
854 131 536028384
727 863 464979071
784 818 67849096
768 108 344013697
158 745 78229559
731 173 126273064
368 538 120757519
609 39 300298575
128 769 839335097
259 604 315237011
406 41 812264266
124 637 429307507
377 192 177068089
570 639 769117890
226 200 66377510
647 8 873270043
503 768 969619521
658 506 219794985
327 998 232059040
2 780 199236261
504 783 794450166
392 158 779696659
861 750 411603963
606 663 403767020
288 83 761153652
698 134 20469111
616 156 479097929
839 438 209185862
5 213 136365350
685 861 168790570
410 913 926922172
96 635 391214600
991 612 655275393
285 52 10218777
471 503 975970552
185 817 592965821
627 607 905674512
92 563 819535185
360 84 307036059
825 725 706587241
5 913 809504585
367 298 22678176
247 240 696641794
539 442 385419261
184 884 243401164
354 512 205735652
764 916 379022588
573 107 666505974
338 964 836323360
99 983 533013604
423 355 699205562
173 50 377920984
610 161 343735575
440 705 976633124
874 200 97233388
436 347 593793724
772 314 32181815
26 725 768562985
854 39 829297962
106 694 120830156
539 893 401298841
868 554 892518023
895 215 94721723
853 314 693217271
842 144 727777985
202 415 160555253
302 532 522121522
814 297 543720337
152 14 755904012
421 148 303664965
976 131 580871388
686 912 744966851
814 91 833945890
197 894 171659458
741 793 852292827
43 180 596395771
634 157 776918730
945 551 979675155
494 88 86581318
191 810 118117867
434 114 391808143
728 73 680210494
109 932 184522476
171 867 647033574
738 709 951799648
876 204 301494125
782 399 332460607
821 557 366497967
571 21 180301354
76 138 465453331
457 294 33282174
526 715 861377154
38 448 130517840
555 578 532270378
218 992 221278245
567 515 561475564
555 284 884317758
136 561 147200217
857 463 137517597
846 827 26973600
256 956 654492043
997 526 177376324
559 789 632139805
201 484 908671090
499 532 798573751
822 965 259198261
681 272 864528481
180 277 427890659
595 375 290768686
692 965 872085539
181 355 763062740
334 441 235344395
439 571 484249225
277 79 501108826
429 93 562804972
490 176 123368170
46 229 683321076
701 442 863787072
571 302 890475025
232 864 164818862
46 256 706977831
304 473 416473617
311 879 675379743
261 323 177363732
199 765 205882051
686 252 895117284
859 214 441828924
404 347 324106629
141 233 674598755
149 306 637931583
992 515 40188515
119 306 7883628
262 707 687362920
680 950 809976201
867 999 952455633
492 466 534299544
160 435 694852954
449 144 628885364
858 399 609215830
197 60 214257630
622 736 860146167
352 698 32405270
975 439 649004662
391 400 276413036
861 539 241004750
384 795 384670159
519 879 434226542
617 213 531281148
604 6 93161247
756 701 816276778
697 448 254086659
778 161 226051959
165 904 643708176
574 608 468450761
437 748 731989347
879 85 940167782
431 220 835017277
540 625 630229630
478 668 114379432
52 644 668980462
926 484 647595039
434 619 309133367
279 339 243776410
569 657 960538615
240 789 255180778
962 664 594473342
898 652 696931513
691 26 58532418
275 59 228024508
498 232 767883009
58 558 782889552
522 44 670372199
384 996 655507503
345 145 194362272
31 675 355795673
921 164 2710337
506 996 877923447
591 463 995465474
594 440 793387347
822 707 740927953
715 436 352498402
293 242 541705550
388 941 420639277
268 851 949932167
922 21 800305131
384 899 276544118
617 650 798965333
202 819 50132907
850 211 132725033
307 83 632748377
236 556 994124102
151 718 500311828
965 42 265518392
658 288 762576574
476 731 132793480
735 742 132450472
554 443 797373717
778 451 212076499
669 273 786245078
605 399 683440089
414 464 17210845
682 957 602849096
556 973 330959878
458 837 172589153
776 179 60986326
585 460 23725105
340 204 359908
417 25 375602775
416 59 546330306
305 158 459820896
789 852 451393139
511 201 540484097
326 119 865190591
385 961 132155625
892 643 590092856
81 644 3668119
715 85 974988499
296 453 930063100
805 414 242118463
825 722 827910276
445 512 883930766
912 470 778680258
493 164 265689703
371 849 431318559
202 780 997158097
131 525 948221647
991 461 490427495
974 986 636684972
628 516 878623731
390 301 246848632
775 747 535250215
661 83 729251071
256 474 137172289
504 362 308066661
111 379 116217462
254 827 196831672
980 448 790635481
390 76 662337091
558 789 264103695
635 401 89305852
982 736 831159998
257 73 346551873
91 504 962995354
505 490 830685985
471 334 868868778
879 874 641150133
166 765 338463090
663 255 458871210
226 955 920131230
645 46 555799736
131 90 851086481
918 70 69240226
834 728 142325812
617 661 130693052
162 860 847774138
919 626 636787135
295 228 176457953
670 1 581740253
644 41 886745848
344 902 795364415
98 922 519096748
155 401 367619926
246 721 606127572
597 860 590703506
885 353 35992479
505 647 250259838
502 777 999836929
869 196 813652064
256 830 238912154
569 241 130209669
465 877 276394545
944 203 32886948
89 746 270177014
378 714 342043012
373 263 831505222
532 378 312490681
742 399 532986004
708 262 707458331
494 366 560638257
542 213 72303559
886 972 400820176
321 836 533983118
910 514 580498113
554 858 444102198
240 52 844988506
945 211 61009866
219 678 595377927
918 496 298124242
48 292 360389
818 247 591136375
391 47 213393136
749 520 21641561
864 946 100950393
858 583 179855635
276 582 846998123
485 813 658044832
214 360 831732457
918 298 421960044
531 662 942240711
877 234 778627087
986 814 566160222
516 619 379083872
977 869 984332820
240 373 613485154
402 992 300552130
970 592 778977909
216 630 317827100
323 576 133849217
639 190 756627652
406 90 373283863
891 581 514945285
16 876 887079199
733 152 269180729
368 706 869519426
927 901 285409200
484 795 187341697
629 692 827470113
288 562 707636651
59 144 341005010
558 164 955537152
44 234 521337713
262 506 20850115
999 482 373368104
699 429 451325996
617 450 675971590
359 210 279618805
954 17 762103673
249 693 347697296
66 349 104652122
797 69 283462058
570 713 609955221
79 90 846341580
253 378 853192171
660 461 769016129
90 232 364832482
878 565 77296444
869 370 25647951
689 10 212682319
759 694 389239283
827 989 778495295
355 188 149068097
56 225 277405651
708 838 459932003
595 544 969782671
554 121 336164716
67 674 567757132
757 356 929922322
983 831 224927791
421 48 455029915
627 761 161156402
348 943 442414202
183 739 722630920
287 994 844764676
383 259 586491433
746 838 344436586
964 45 992545033
264 680 622827278
344 71 882451847
616 684 999141916
897 66 988110828
782 735 886607098
836 866 2297374
831 170 886069301
268 396 730061856
1000 536 418829098
82 652 984855847
364 299 632323050
771 27 624600807
103 191 728455067
935 721 774529713
321 513 55950064
124 654 643702120
149 732 991564313
723 433 880951773
3 81 890806836
362 561 25464557
299 902 894039070
688 729 117023764
374 904 660412984
782 512 82704139
356 210 97269996
681 981 876910729
906 597 869756451
142 595 324662048
823 113 941540262
855 684 98175479
475 851 119427559
659 637 525212816
104 63 164453844
535 639 854132800
863 848 56105480
250 49 537321932
671 763 17003171
905 664 369129102
249 267 670254747
538 112 362148865
451 672 157162278
885 310 59069831
781 652 218053175
284 111 213714684
77 952 798529095
761 359 200821561
562 366 290343384
267 705 870734247
275 629 985281610
563 877 65842605
587 428 273591675
393 456 537639991
362 528 542598849
886 595 19035758
475 789 284308492
34 309 258217980
800 908 700377366
930 451 348915130
752 75 166601431
720 1 338083918
184 825 261618355
132 242 326413794
943 471 84216011
11 847 206948481
679 333 580269149
220 348 649176352
305 764 117458005
574 749 888514657
769 225 99846067
290 498 624086022
667 501 453479748
708 667 352966372
451 587 566305744
748 749 549458105
187 805 445642345
103 303 562362406
212 90 720835564
113 725 833311512
733 198 208479678
120 879 164762746
942 72 423822747
925 571 985082636
606 444 171166620
500 328 428632150
673 416 27553068
533 324 205901246
689 542 158678191
560 378 774832103
695 980 208419463
591 283 360777718
682 294 294166250
306 564 980204128
739 375 110908436
135 18 834909898
74 995 226126208
142 932 549145356
318 354 112823892
573 173 158510607
365 218 904870508
104 401 562999951
102 763 592651012
178 728 84762952
348 957 593971410
100 861 311843464
171 887 436616116
440 526 458739957
148 297 938871806
160 402 691942225
476 864 799900753
776 365 758201451
189 213 575980192
371 951 874446396
796 947 513792944
440 478 500998397
391 455 582213351
182 393 310378783
420 665 693647921
613 207 332737033
394 191 68949611
432 31 841927644
682 384 941685721
366 625 7157406
466 70 482886288
653 790 960417646
701 189 425140958
697 210 367225559
716 883 895167083
890 249 493465293
268 65 22852432
816 607 286564098
77 238 772351415
160 752 371463261
593 660 191094443
573 331 520004128
651 841 558761033
774 198 130381639
613 961 359154585
399 39 50253703
267 421 943326688
892 731 14844657
190 588 136602581
670 73 504147244
424 505 500142027
35 907 955095647
693 943 870624808
143 936 292470895
449 210 658934691
289 246 983051109
643 644 362297549
826 152 779552981
493 367 443702453
769 530 804316936
961 627 835245176
234 894 190500341
383 917 480325216
148 842 289946926
374 634 867566867
500 623 53280979
159 95 229630658
208 861 832944940
269 448 795851844
325 958 287000465
775 848 70718476
325 864 250032154
5 252 744585135
81 870 117661389
205 565 279856343
981 896 496318636
832 444 192338882
981 597 561918642
390 695 569355452
6 646 935415696
130 669 449781965
62 983 522426674
409 13 927904446
505 143 605245005
136 246 683124158
203 591 850579000
533 75 78175722
237 546 731504789
111 264 831482386
470 754 680276470
549 986 640508981
266 628 763043220
825 806 612198554
144 90 58491554
709 489 223809070
76 779 805762275
912 36 629550881
406 458 767855561
710 422 713448759
950 784 314237027
193 210 862024638
150 633 610804624
176 710 532775774
1 744 948172448
199 842 160174009
417 313 549807468
681 306 407282456
173 651 897329321
19 36 328076834
804 983 704358989
261 24 12892289
265 387 164211886
537 74 624592186
166 33 701651227
31 206 263167678
812 541 363854547
390 365 903933541
513 165 84014723
148 61 64465626
911 502 338300763
889 322 103337750
433 377 736019711
192 283 459910352
613 505 95819635
590 748 299714236
786 555 163428291
716 720 483380802
976 934 271187052
296 235 330041068
481 509 496585407
325 946 453697806
340 536 136703873
312 963 369825058
16 289 504864377
554 594 972896085
70 372 544633611
950 540 816005078
519 56 63497849
504 934 411104424
981 170 119851575
610 46 777445019
421 847 728904203
865 390 379283578
292 31 775531002
322 986 363747647
410 10 317868136
139 177 310853434
405 141 873604997
2 680 690626428
951 201 878023497
139 257 527019920
971 379 921566319
862 51 41508509
462 47 404529917
195 974 119547915
680 461 471345262
636 647 534201245
174 106 562751132
77 82 440506761
952 35 466206373
884 627 683498085
377 877 855445610
269 300 216607772
306 314 985316429
46 470 751605994
964 263 954533036
507 433 935825677
852 93 39473401
350 385 502973311
441 839 906765409
233 480 412543827
78 965 428475249
709 288 585558101
927 162 314240573
502 29 69386275
781 601 332265289
312 173 181926308
505 89 454180546
250 967 518539518
653 627 509607460
868 885 52620669
756 44 926916487
203 170 580673128
878 116 124012440
719 809 263665233
121 463 326788102
568 204 366482990
984 182 742854311
470 948 746350998
346 815 381918528
252 577 836511385
320 109 358247785
246 855 28465279
484 529 178103050
284 637 265965867
991 935 280299104
563 33 444367163
238 653 763408780
790 515 507480071
799 493 244236072
751 17 584125391
879 192 178431208
976 740 346675130
676 628 339681629
893 777 68643060
373 872 626151509
787 423 872041633
43 153 378948059
918 991 658153229
477 416 142207492
592 875 797462625
985 326 41545791
459 173 470345883
545 225 94281716
748 128 703184186
821 481 987818235
211 783 807793976
300 166 834878814
702 236 707188460
4 223 24126000
223 217 998055733
759 520 250815392
841 728 203234119
509 623 642056018
883 985 678258828
61 219 666691882
3 54 378584311
19 517 48515036
6 175 796453668
891 864 933671889
911 362 679463542
850 801 753111974
459 671 595934263
516 111 582875301
249 522 837212597
834 298 917801562
820 171 630570859
197 873 425289471
908 434 94506909
33 516 754305841
47 528 840753303
867 968 860995549
419 16 686043875
522 816 187011010
725 108 836965349
94 767 926102883
557 116 634466320
823 958 624496628
522 243 480697588
298 915 222336035
218 984 469391997
464 467 27584845
305 47 494809291
689 466 583469331
367 732 278494476
539 328 507773618
608 726 310086162
235 637 636197109
715 114 737322906
406 229 792480784
169 276 708559315
559 876 501069432
578 806 216957288
108 393 416352965
344 236 898900241
599 911 877068485
861 445 499511254
960 151 402307870
977 195 976576637
645 282 859600289
930 158 418242254
186 706 340602408
651 961 715303404
682 620 679478599
495 575 850215837
341 153 498605744
365 749 397616926
797 489 57279826
108 540 46654983
676 898 45705099
419 990 481502119
832 2 381957853
179 929 941217580
391 188 239424917
902 649 646917463
753 744 492169762
703 930 515870607
341 979 229279168
496 238 448112700
23 852 613267968
954 238 994500768
308 399 797944067
486 950 332269302
431 960 852146044
449 673 307593577
155 53 699645275
134 803 189114971
315 84 554548181
529 525 247837758
430 421 726556727
197 302 130616656
782 711 145820161
747 254 988327541
161 886 641644622
478 299 243491759
670 595 787017286
253 476 841473844
598 683 525428180
459 995 832098633
558 372 74968958
298 268 174688821
530 843 19755351
704 801 155918630
659 938 840060222
293 498 433856920
338 165 834012522
278 803 873619884
237 224 952784521
795 633 58458043
656 681 873043364
27 123 912772414
264 715 922075567
27 184 414031709
315 828 17637205
256 761 697486491
251 301 32812192
520 863 656335335
837 428 597275554
654 398 397611370
653 449 175297157
172 198 825985854
107 442 80093820
361 718 893560961
276 985 396855139
545 387 474036706
158 1000 893414151
499 688 572770176
832 293 372322284
864 703 829771419
757 6 892185580
592 266 954431096
383 84 211203684
448 596 568969116
84 113 167197167
178 609 448407272
359 598 356459410
772 72 686192341
438 92 457167296
398 601 494264217
192 465 379234917
924 92 98765336
220 482 644994789
961 708 806250303
20 688 984603459
512 727 460695736
291 134 803275056
381 918 95882438
933 860 182261225
313 242 526671153
187 457 28429106
930 846 852801849
239 274 359810110
385 459 997058784
5 533 127059543
825 217 819513591
546 167 327453873
499 774 102462935
153 709 993179476
727 634 921228792
598 169 85347464
520 97 473288631
407 168 623508261
750 548 695103125
881 898 194751332
783 787 664326037
737 40 862641524
198 739 768012984
620 559 728306710
259 174 211394616
481 636 878804528
469 862 973285002
991 843 394914609
140 465 743381421
82 778 453850424
657 387 266446665
314 65 200416583
870 185 57595105
706 533 107983953
198 307 192285951
847 104 931556412
469 211 511328013
542 556 69986057
609 897 872633502
973 467 656916878
724 754 465584813
101 482 28879820
126 665 15560399
714 159 659128910
858 974 499212094
551 298 335073704
72 486 95951265
956 692 781483938
181 80 753861293
118 520 392940740
929 212 565612087
535 572 183590392
211 975 776768057
590 91 53856314
232 885 569578224
949 198 14991387
540 128 874988952
280 666 680661627
218 737 911983358
837 215 513164409
887 711 862127304
973 240 159151489
520 906 69846926
806 700 499043254
719 619 234666925
340 38 974633004
975 311 934328519
499 726 817713537
579 444 930046559
595 632 843747859
279 243 31333702
487 355 792206116
592 146 379530657
242 477 542704293
859 572 279023334
254 831 815395729
8 870 697130200
58 820 222094167
628 928 61063561
129 184 627318952
415 939 408436469
489 777 657396673
806 514 414505316
603 738 820799090
339 256 150473412
561 121 552083498
27 66 219094256
388 944 305509246
640 568 843314225
174 28 346065361
384 994 32030225
280 466 619591657
873 150 435236073
355 736 354548800
439 146 793659108
93 812 827580806
292 466 85067993
170 818 544970297
823 895 795768397
577 332 788831004
673 455 758838251
734 559 949262491
699 731 569334321
719 85 780870797
267 878 836807713
726 537 268837785
589 529 546328906
808 367 132876125
624 823 313089553
897 429 286584943
448 745 94524579
99 900 892204228
81 430 796542507
312 713 294404121
945 200 260031170
602 419 533050863
219 644 155625644
51 463 522480762
428 170 908172605
19 957 237229874
874 228 53837285
109 988 318920782
508 562 695666872
165 678 449585357
167 740 761426157
704 309 662786594
790 47 462232186
382 100 325588052
951 594 76621671
510 516 308344437
215 284 876736892
125 911 294901929
762 488 484807698
106 149 202764826
882 699 969671802
698 918 191807912
834 655 706314323
287 984 143675075
390 986 907415567
330 412 597573214
977 289 422454673
965 161 549147898
638 834 445781655
816 517 888248333
168 360 477759535
134 99 882618193
217 927 521345048
767 483 227404532
324 786 41623582
450 200 218717089
316 402 160683297
896 940 794150986
136 239 789677308
798 690 769013062
767 554 722887373
363 546 319775536
461 415 527658026
968 58 987886322
626 324 509511397
174 100 687496736
601 285 890159486
700 394 204078188
673 201 951840389
119 477 289798194
170 211 9362904
398 351 388183301
211 187 8663859
422 837 54387001
773 579 864155847
158 137 155946737
830 427 331371382
8 492 515691964
539 528 422313795
636 816 746942560
408 310 278247410
548 999 622377680
133 632 246462881
452 917 408050368
616 283 687537440
175 549 979026732
452 307 669544552
996 149 585244574
63 7 323387554
882 808 338472676
799 796 521166316
692 202 206617975
565 78 56218393
979 453 400701090
12 761 161556305
774 988 912853837
280 277 411795716
583 434 449993202
500 852 270791509
833 826 848541818
909 921 513055266
262 898 531214043
779 259 400683966
998 477 255714033
551 647 141518011
987 78 81930089
153 546 732831567
249 974 440778605
331 223 59941535
579 597 24976519
509 148 22513258
598 864 288095856
604 805 266889303
349 908 60866431
928 489 45710879
233 708 421303577
256 917 779735747
982 390 911147500
373 148 840813347
71 300 810424742
726 87 918717348
142 868 550542705
6 914 519716640
404 198 656406534
269 580 378899194
863 918 190600901
170 360 495288267
124 272 693704365
961 726 959275316
730 576 356800554
803 91 447541141
481 272 862784648
195 533 784435636
767 173 589602020
978 864 305443809
289 238 796185459
268 613 190700738
922 23 1281920
994 735 580051373
530 948 614116555
870 766 669589821
595 377 379118551
944 839 841750164
780 200 193102917
312 914 500610753
87 833 895873040
352 337 417470317
796 37 54681349
137 1 183635291
495 845 389058624
824 265 942564162
611 729 654810441
955 34 110119556
190 875 714833597
754 661 478690012
99 549 682815396
994 985 381927411
921 196 733058515
197 585 886771844
381 992 422354316
841 233 133257414
101 90 147824957
40 349 979262021
719 920 120822750
319 946 676507281
252 791 361141008
897 542 111193907
524 949 717325200
760 324 268868914
264 170 74413485
38 625 882405674
302 124 958163596
889 926 736603983
995 721 976966961
553 887 285419833
625 687 520981034
661 337 692840849
464 839 986308605
975 736 879308449
920 311 331428271
311 9 920119021
987 768 429711488
309 735 288061340
679 97 439957080
597 749 456502188
76 51 792216302
201 176 605200452
777 510 58267776
575 322 472530927
849 40 268664044
654 808 39288426
653 443 380990985
979 830 501423543
731 798 42806528
79 285 16493179
468 778 755477061
382 937 772539521
366 331 881241888
859 672 831751516
370 853 579994497
701 669 980475812
932 763 385216580
579 44 870467002
166 180 156016100
337 467 495317479
996 747 821386001
784 379 624795240
578 518 77453342
310 61 626570393
532 769 602756438
670 56 266523690
602 904 818845862
883 355 480095023
635 663 65585038
319 194 560365751
400 397 691030299
178 25 365897163
93 825 829230455
663 8 493132044
341 120 185506164
985 180 151086555
178 497 542873984
39 584 615448680
214 691 371365291
115 856 347841452
753 931 635660197
11 143 303646895
225 452 19077913
706 263 432191117
121 341 687148772
220 194 70531701
517 346 109073079
19 63 531447350
373 859 464011159
357 886 896130623
158 845 554177841
653 372 931459075
984 626 947147870
635 204 369782874
83 392 329717205
123 809 996607980
284 452 640635307
856 82 314054885
733 216 305817637
361 507 607257612
176 236 476661365
882 255 138840911
826 261 420328707
569 484 342753286
246 92 392002058
902 893 618699521
781 844 572602802
251 3 956772972
127 60 815464719
444 504 884476707
14 166 760368820
514 802 327368629
188 910 948756859
304 638 457691260
369 809 565808646
479 164 74716391
80 845 55237997
240 525 875389501
253 667 259197455
392 82 209093739
728 936 587348806
540 346 510578236
713 505 621234426
690 354 632831897
792 613 115700252
964 425 879121152
604 225 734284193
309 79 934161471
593 143 684312064
991 89 610983846
561 996 486505778
447 826 841761317
856 560 878670245
918 475 415983553
895 115 623905909
731 339 169226163
365 648 677540854
693 657 485638110
933 124 256124339
769 884 682354778
37 948 668892165
730 767 853638190
201 904 520232783
828 224 661308227
374 217 121127314
463 923 760214577
709 879 119624902
323 278 928192379
308 629 937192016
180 467 407698421
243 806 980208793
520 712 483567325
569 300 734257405
383 827 671126898
10 487 273838265
418 185 299697204
764 781 575545005
426 102 407133770
947 941 268680966
69 386 143998465
719 88 360775854
379 315 681225520
969 418 781108839
282 210 71715906
936 422 147798598
19 528 617613260
554 721 173156261
825 173 201793344
181 424 302563109
901 959 275626127
791 413 632841537
957 729 181990084
674 306 684263889
83 150 835603300
866 830 568479002
852 86 168422980
216 983 165122695
742 637 136044662
569 36 962102004
881 809 372558694
607 665 320710452
971 627 914763113
393 533 94365551
299 491 94165323
89 866 369383837
237 793 123501214
738 192 801113846
623 152 610784526
462 474 813672628
151 758 761808801
944 335 62619275
183 690 173092173
653 259 968180734
851 940 808862071
641 123 260467818
580 933 612313818
408 221 584101295
563 931 624430125
496 178 950880265
197 627 1364301
364 858 228818135
112 889 257500786
543 934 17701406
302 942 436298457
564 835 433489998
394 497 75916239
404 100 713052408
515 383 96533982
850 871 298280116
93 692 89109679
730 518 217219729
880 110 87470814
640 566 344888631
654 33 677713497
276 406 218737725
351 464 182598652
987 578 652022137
993 374 754606617
391 100 120537800
477 153 431819054
638 241 822828670
264 427 854924121
767 227 803983012
404 645 14026181
360 568 435612059
535 811 6576370
544 546 884849534
684 86 111162724
440 639 113529512
861 356 5663393
889 21 798858881
491 622 711272937
393 666 104901942
761 37 591062830
830 520 120344743
999 946 944441144
432 503 950788780
676 226 638440849
847 775 745672230
586 751 438678483
690 799 629146252
769 596 887975552
337 394 794857810
412 423 627072919
901 321 252755726
700 163 239288882
589 366 568417160
679 863 508710635
84 788 276777350
321 431 142330968
224 75 408954755
793 88 808115391
62 332 664412237
466 118 150893955
499 951 927683024
288 994 960528074
76 451 953541885
162 756 249839790
953 22 853075764
953 413 474794872
74 768 263545968
483 497 418362655
728 599 840267987
119 439 275259365
763 508 598977185
917 446 157168483
95 664 210712712
60 685 992855599
489 619 597412491
994 236 56805187
343 16 790305089
54 506 952122838
803 52 629740962
939 433 880711860
900 8 629662322
1000 613 386032446
11 119 955980073
661 584 384262799
285 853 199586016
870 375 711973980
739 682 672589508
664 142 35857425
767 664 695122214
661 909 711225075
960 160 3731514
539 324 395841926
820 892 249600200
708 170 546591868
847 519 765033944
280 807 709555011
940 467 645180271
539 438 810168294
981 879 731528220
743 843 70474385
33 108 51876798
443 351 423166088
900 207 459412820
723 989 722020954
6 453 8158255
450 256 817477632
453 750 45781410
36 972 35940597
251 753 118611092
525 134 246140788
582 550 343334780
296 645 936482009
217 788 438415536
424 256 426349021
714 970 265723299
323 636 983831762
129 206 970350319
126 517 24166292
710 363 792508069
774 270 986292770
39 373 92530018
395 422 867663571
936 992 814925583
537 998 247849220
300 285 670086151
532 602 171759759
325 741 392405364
368 936 689876766
571 718 875400985
330 713 744974065
266 961 910869416
220 357 831201182
846 913 207531805
631 440 851929461
856 704 784601226
271 730 805728325
572 518 666402587
968 869 994238406
266 243 573675274
23 564 648688137
197 695 20555654
508 286 483079175
784 771 319354765
530 462 20260634
197 567 238929621
235 560 327466021
430 423 746872935
131 772 366231730
375 154 554888842
636 334 239566284
514 768 659865943
534 668 593312478
667 39 652400556
864 353 806032276
363 777 988669067
662 383 34673956
827 275 272540839
832 518 429531309
343 746 708203635
260 513 606873293
421 881 824457874
896 725 78332766
693 462 617781895
253 835 716161825
131 939 556777458
31 712 668927084
160 174 356409679
473 526 268247075
888 303 741157424
98 834 353936461
790 59 289852584
300 495 366875779
852 468 96360918
507 937 963095191
20 785 948738539
607 685 258633862
812 671 964557888
410 742 771178078
340 301 694973139
753 887 205686764
159 781 229539408
989 866 798366822
201 268 329187025
773 137 3318189
233 401 381834809
11 190 900833926
920 251 744925956
718 426 589587253
791 579 448804692
700 462 72273802
356 792 12848023
29 600 5139836
219 278 95178485
122 563 646852552
652 232 723231883
922 568 394959993
28 655 752511624
292 768 127166966
783 238 826132465
775 822 156045862
47 753 257835033
130 978 992206577
418 91 574364360
840 888 118444500
431 56 533260137
573 245 783988843
317 285 480344218
419 508 2810124
924 571 304750815
969 336 637349198
660 401 989538057
258 670 745132585
472 719 259946998
85 791 333804815
742 95 32193454
573 152 239995606
61 1 91488872
145 751 969116796
594 452 365457463
244 697 778965308
606 246 566040253
176 257 754508322
288 477 405948730
428 995 213681015
318 217 366302976
472 421 945376094
730 704 186822861
288 712 272669605
571 284 449366294
30 477 29253742
548 393 297278168
520 656 416737730
621 13 370534198
22 556 25756850
302 113 730895068
125 824 512669299
808 677 282359456
214 68 726407319
683 383 678611197
877 975 527224331
458 257 73152311
172 113 831770409
25 14 234218486
627 803 41876437
375 501 545451098
295 185 585895163
689 773 221807497
22 40 672060996
887 356 683318372
828 605 983146678
736 556 669986838
549 770 53978178
410 817 612079714
742 367 498260343
799 358 536952590
103 123 253989796
551 434 762972112
450 179 737025695
304 490 312598261
684 710 103583329
643 266 405435063
742 945 524139129
571 632 745574497
711 375 42983344
280 328 877332079
699 613 698827378
302 903 316516908
735 962 727383628
705 19 817761238
657 298 115334778
916 846 601274354
384 679 800223469
731 345 99450003
194 989 834896525
252 709 791959681
882 900 181571652
731 681 115377992
565 766 224360639
503 605 568495111
791 31 506185784
900 217 81898132
858 283 956373013
408 793 286739670
410 457 682635037
170 630 22394368
278 319 571363678
181 74 677941421
175 481 430793956
592 475 711905652
608 806 389154460
655 29 909626008
237 888 38353866
60 737 568489488
869 282 614670748
748 232 821227541
672 862 725430812
588 550 342823146
615 164 188379292
301 403 818555768
952 92 671694429
321 627 243787104
138 688 936174676
300 613 926093667
209 754 253668920
957 797 752127009
513 448 908385496
462 214 810183930
681 738 773109356
194 273 157572709
602 289 411131069
719 470 21606752
479 361 329527335
156 531 475468772
620 101 95587030
672 415 158658594
27 875 498617023
587 364 540605926
972 523 520406270
405 216 263639635
653 23 697799164
334 557 208975031
785 748 340468780
543 888 401804287
376 53 140726930
841 892 859832504
742 455 748896008
486 916 621368834
895 68 312066326
845 818 928548376
485 242 800933773
82 726 579742909
802 141 63231323
226 64 116317704
613 467 398927240
390 864 986434365
443 755 261567771
220 509 580465462
175 595 15479650
131 260 400579057
403 425 553201391
583 799 530002246
360 863 222133274
850 102 854355324
832 753 955888766
852 141 431732497
637 992 10332601
219 198 112183031
209 694 894554343
396 57 552588754
223 569 549758769
919 107 979134235
168 383 652989023
137 170 205676949
407 927 919156917
164 713 652229744
974 733 72205837
24 409 639593660
153 232 125420123
677 818 689614894
319 51 551613081
648 977 411405277
587 488 871596936
655 187 365271959
871 39 965120169
660 588 806046334
129 409 381486016
195 344 810547974
592 934 996547696
763 522 296626623
416 469 124131868
42 599 20556107
494 661 112598856
749 57 61212708
366 58 345649836
315 760 387651167
312 418 245613512
677 297 123386969
63 993 89437863
23 706 326710892
760 152 802338639
496 677 175160204
231 462 77960811
122 958 770944227
874 185 667943466
921 784 816666882
908 932 718929058
703 810 587014180
176 461 756174185
430 606 854568318
139 278 855331140
332 932 659995857
408 780 187251291
126 867 909052027
954 441 423643016
932 295 923855170
125 154 326803171
933 165 976702483
270 150 766290110
597 858 192965215
575 215 424573166
455 533 729892356
20 248 269687258
28 269 547256967
959 382 646227712
498 793 369224522
926 29 394782190
651 26 144607293
728 674 962663980
335 316 167317956
973 507 377726373
230 171 615002761
24 512 680296042
421 612 221461149
723 424 435058028
920 337 431661144
843 660 377100120
97 593 255021127
317 221 862001636
635 714 868591010
870 211 800289060
555 235 565094162
50 229 487282633
997 211 745716655
892 493 258291983
519 494 248258745
687 990 161622365
280 289 36574776
162 879 730553275
613 640 744957800
266 727 83868006
961 378 9751430
464 921 696445295
873 573 432083128
536 447 782030385
217 559 957624553
115 372 893014992
826 586 288730895
32 502 539419227
252 696 565048466
908 513 319555690
878 59 643120989
930 56 269908394
699 325 188644909
260 308 38598807
617 356 688173232
278 92 527580751
983 672 248746361
183 35 477270426
275 445 408309577
737 974 789131307
697 910 986171365
123 584 893615852
843 30 630108804
675 116 356187342
110 68 323069062
649 456 581849722
379 211 211762135
671 837 574940187
310 849 919503390
482 322 366018406
674 613 440434190
942 450 909047189
685 68 284610062
584 572 322869891
159 409 86989815
92 35 946511539
735 78 228318157
559 250 258030278
473 502 702227210
266 1000 892515129
522 691 547056867
364 834 740331360
305 513 547796220
228 305 454111368
723 933 688581572
278 959 801210872
152 672 57177419
610 804 344536641
54 466 639277181
6 419 744639815
383 406 141346174
12 509 166615250
48 557 355069055
981 356 495184559
189 896 215655139
135 882 541068709
503 9 840968442
307 755 311520263
938 121 269373773
15 241 860862479
291 463 107064490
543 807 569662588
346 155 972050244
920 603 202007767
216 197 340586683
714 299 205735413
872 195 385554596
144 609 472008178
580 233 26504326
224 231 949712316
81 622 691343559
965 459 710113716
511 747 320784742
178 880 604816316
531 991 362267358
390 872 915088116
497 422 764343232
818 425 644802036
456 193 999477308
966 456 767085000
413 519 783900684
991 979 832992939
90 543 73073491
337 621 750394026
473 928 994559190
112 982 196337621
179 880 975672584
527 521 18616158
30 48 848427453
675 944 593247975
776 400 890314968
758 323 922785033
691 433 231126014
805 272 240882968
589 373 453943443
453 793 889792203
449 220 91506832
724 33 243645506
52 224 400027774
3 593 7380858
753 901 214389076
637 75 312270637
699 453 210398699
788 580 796990178
420 633 524268692
724 503 859177990
340 915 611044647
392 864 738756864
482 135 616852858
418 302 608966208
333 526 320483895
176 979 394163311
739 179 530470286
657 327 976875008
940 285 828460836
907 420 799010377
937 274 235521448
851 872 809420794
912 964 844504306
825 259 939728250
277 799 9696015
685 429 123853302
465 257 702908023
607 119 926883025
198 325 730054391
300 865 375420479
987 362 753224473
553 503 963603176
812 642 470721564
481 489 603667096
679 320 829074043
914 217 353313915
749 364 655014255
303 49 707675200
184 426 123070932
174 862 925689419
857 344 925388131
695 56 436406707
684 814 286378190
845 931 392126023
226 865 20923119
763 746 920584753
170 574 963821897
795 628 418727272
480 310 821238118
507 310 409770683
359 192 102102322
342 695 377096298
306 213 708699242
626 594 999629985
276 894 191850957
473 884 353623655
388 375 489268612
746 671 752452783
617 29 831377082
818 974 895665661
697 679 872604955
234 516 971710875
495 715 90027597
945 170 769618378
359 543 791152794
912 203 255048207
427 197 173348453
424 375 67654827
57 696 515540155
538 879 870292802
841 714 514155847
653 860 457239042
802 707 394662489
286 566 904869854
729 842 845093678
802 76 522796029
251 780 53782770
944 219 321287920
886 144 543245230
531 644 160398146
301 802 538746352
757 910 715965941
368 899 707148161
742 793 559076608
556 65 923823882
737 832 713233795
789 105 515826588
392 742 532332002
751 829 128750204
980 935 187531578
668 672 262994579
69 250 808261276
74 573 759968782
981 673 833980078
280 962 733555666
873 548 24818356
528 587 417182704
552 133 973445896
347 784 933417394
463 133 440077992
882 550 963819232
256 287 202464753
954 267 630081203
768 107 905603215
91 284 413931198
780 577 402342209
621 550 92986109
471 786 405540043
485 354 44403103
608 314 919921909
968 660 975934241
135 472 304518282
940 831 402833553
786 399 191421615
891 758 475804438
190 863 672955053
744 100 536721015
913 762 816741539
723 172 183625109
146 918 696053578
883 691 527068324
933 593 100499848
639 680 231063134
829 306 683965481
649 753 494434089
457 419 708423587
670 408 8968446
129 759 755318523
721 704 101432390
414 312 312695112
347 96 58221576
115 63 824487779
590 95 409072610
344 783 19780281
717 320 470998940
549 781 321642337
660 792 292028297
94 766 130884188
591 777 44623118
940 513 566782271
204 548 19382867
468 194 384081776
746 276 283233217
666 877 935973516
803 634 989742061
623 495 603852560
640 392 33302047
505 275 550452154
993 378 300392878
907 177 340015697
388 552 861343705
865 541 466553280
102 817 771904210
182 189 853943095
36 363 271367809
764 191 918958737
483 909 21752142
853 245 654668986
357 902 179311247
349 370 174632748
35 269 640604023
634 177 511911683
610 476 751684155
655 302 412972290
14 114 569716235
408 398 173975215
713 403 965511440
872 364 195976400
232 96 398886527
84 504 476113386
895 942 151898087
146 289 808766141
915 350 47882609
294 957 439375869
203 667 788953517
549 397 734905660
586 2 92981545
840 224 918430745
873 768 125908885
404 700 661212471
897 661 303657846
472 840 934880367
463 667 724628151
420 927 981153868
903 285 128254581
16 118 466063689
896 493 642386664
887 50 143809369
456 424 472371798
360 790 357717549
313 853 690600904
492 732 541520163
292 307 957402145
340 943 401558954
369 678 403109643
919 330 768209970
440 138 599108408
890 769 752737672
230 516 725566874
733 341 432632906
182 123 252065731
462 659 960668988
576 317 383098379
241 890 765124700
820 30 417718471
818 544 548829563
694 394 534420624
383 714 552292466
301 710 524645518
459 425 153675857
42 584 300273045
225 805 206197666
64 580 332783315
828 808 916659784
824 826 829941334
806 949 784105420
94 447 54485341
12 886 127849470
908 21 2115407
760 257 614227332
567 422 500348696
311 174 262987381
656 152 186649299
638 785 195299883
645 67 757112350
445 296 129516346
30 439 149868165
535 566 307717943
744 794 309621731
753 783 849632569
111 348 823613402
605 59 836467801
786 334 83736632
807 300 964644647
448 148 10861879
809 823 973236094
671 323 669625507
621 156 674529584
347 289 737365725
517 344 851388546
553 608 733875336
336 714 85201458
206 412 619214056
17 294 461451408
638 512 410322166
936 88 662663104
787 264 835138031
549 919 607599391
90 869 507264543
947 603 306844370
726 916 34105302
323 409 467493599
106 507 16903517
315 978 778251469
707 684 671181880
968 419 812199477
696 361 129116435
99 439 707855789
893 965 874427679
60 679 949042731
79 891 824541812
365 13 153583994
238 921 690500699
290 577 816148445
695 212 902961642
235 470 895099196
146 166 987629495
10 796 19946140
998 94 849804792
120 512 443292656
312 297 410572812
133 369 155879055
743 141 605724329
157 966 54257143
46 952 899088110
187 870 830499844
462 249 459053446
859 400 463144274
144 520 629956364
165 116 737620124
622 759 104394171
176 24 221643001
398 566 586913959
385 506 982143362
290 718 44942485
387 919 81134634
116 545 899210030
193 180 392262471
615 550 927231656
417 29 263490780
10 84 49789110
977 670 491472010
172 843 679475680
547 371 296888959
676 512 220955716
147 47 342906119
105 739 377348267
816 681 666959345
27 404 465412510
863 908 83101826
591 543 365467790
716 752 540268012
437 15 180470038
508 278 497752357
761 768 605900646
128 471 159303879
871 729 298171362
564 770 618283271
467 678 571106448
683 372 612572758
619 355 45558902
952 422 178386657
845 612 998075198
908 570 322007160
888 749 562240340
953 13 845089817
979 949 409753600
624 303 615151878
941 751 568208620
402 429 909080635
324 450 875280157
333 353 80223398
840 914 595354267
807 128 996408786
428 973 528882131
611 774 22376532
512 829 996062867
744 254 664063721
497 568 145704977
905 244 438174771
938 468 630754321
708 832 583363804
82 964 131226020
820 649 278069139
982 652 270669921
684 559 451722649
141 785 9216808
634 962 312481037
809 631 639641079
824 1 225568016
813 1 426398167
702 995 587303213
688 403 907258482
232 996 947372844
863 836 847768378
229 841 223060739
532 553 971011867
273 547 320614979
795 669 316555251
779 244 252352542
935 960 665895996
200 190 914575550
1000 267 659884833
40 13 853098860
340 661 437915870
380 48 906607418
627 394 847817475
250 870 291255669
981 291 843372102
534 180 575210746
343 258 514624697
335 110 327362316
159 580 560786632
97 561 237685150
979 434 611650323
457 539 77437181
290 603 580446530
187 635 477171719
566 901 50734083
989 923 746586892
454 117 257502999
813 727 597925074
650 470 243934275
257 881 521094128
739 714 491246474
450 336 746239658
975 188 425392737
835 98 766942762
418 297 448746771
208 962 7479790
1 248 557130476
204 963 881457358
187 382 854978031
65 997 356246184
492 774 888444688
782 158 471906136
419 717 33899019
996 899 108343867
838 399 420201550
474 8 864581620
860 992 447706016
290 263 370009198
220 64 849102163
897 524 862439796
879 313 505090743
585 950 958440498
590 993 378459454
631 382 511417330
272 253 986057432
984 71 963154132
674 190 585900307
65 794 245399759
702 495 787323710
292 38 476223381
882 970 809203165
260 627 997776783
387 857 312248997
393 370 691603412
428 776 653786995
360 375 969021166
407 399 943837466
661 26 451583806
329 702 33389286
309 982 448898781
16 443 747813129
873 707 923026709
171 54 361248198
530 370 177975761
860 39 858482760
436 202 549048633
606 626 37743118
273 685 762915694
362 918 713651810
586 928 631648057
933 725 274148202
398 629 879807039
255 232 268946481
226 850 34457874
163 980 978460671
525 41 407160047
695 181 695400671
373 551 594650974
670 197 927277678
669 824 756956053
849 444 259364026
60 498 593533535
49 666 644108874
152 488 12668154
895 140 783934985
247 149 770671905
947 728 623708935
259 313 299067391