1000 2000
88 312 190442306
480 402 411574469
29 901 397491243
636 459 323246996
452 37 828529684
39 516 418061741
382 685 301044599
899 364 534095263
362 588 62043917
354 375 579036281
990 536 190613416
756 842 626391500
246 854 757939739
588 263 632978222
52 196 678338775
599 877 631864853
107 497 550050606
300 775 755183437
302 456 852723687
816 500 647076091
543 723 500374820
98 40 749738852
927 30 145202166
546 142 870083810
750 524 328860636
602 25 211610767
474 572 872608095
144 910 203117275
691 234 729284979
539 966 264756466
382 535 629762072
853 609 61869740
162 900 174341433
838 906 516844577
183 78 711952773
79 846 823328129
795 426 104257678
170 424 691448051
559 736 801761852
442 371 195398055
377 616 956274392
87 641 820234462
124 440 713193283
462 727 111168895
918 181 974713986
361 703 550581681
545 449 342617944
829 54 247207855
220 652 545032864
596 85 592313184
320 884 928489453
900 172 730320982
141 708 788181037
648 86 244525100
147 735 262909796
217 742 376974969
309 578 75231822
544 633 634064861
429 740 813905309
437 703 284010346
316 597 340775132
291 458 74620172
996 56 80310472
607 893 197421119
922 732 804019377
117 903 103747582
963 496 721784509
468 766 785389231
314 938 347834674
240 379 752119302
851 950 53765661
634 812 968324946
376 437 396374271
280 840 823130041
608 875 386696432
427 994 850547710
798 418 19982569
506 993 311118606
694 937 403379863
403 632 942471807
821 203 957298342
621 659 26500613
195 882 274651744
325 830 147826526
541 680 682226317
103 843 387074444
803 950 757779805
76 575 278043350
109 685 70662397
757 466 123552378
311 776 690514830
142 869 89684111
867 796 756033225
353 184 577027910
430 350 338542242
383 602 529525295
84 663 490471977
469 903 6971111
717 440 932941448
844 248 193186881
834 298 212778452
442 537 698396540
335 184 760367754
742 282 338058465
294 288 594246610
388 80 563389936
477 973 386962444
157 391 519036146
345 7 307892598
389 700 360690972
693 621 742457542
888 826 549467161
563 282 756709553
787 900 751953110
575 76 290180759
360 443 566861000
34 762 340579921
184 528 313028156
326 38 8493503
217 831 222511049
722 476 995795291
126 820 790584008
56 570 531620837
140 16 544160865
51 131 379966393
41 863 68390017
369 116 645705075
788 140 404199053
788 195 582854376
167 423 453490201
493 353 112488732
13 226 736584610
446 602 589280068
828 693 30928545
492 369 944796807
836 878 706302099
12 403 940720862
232 614 340308766
262 6 753599901
395 367 130577560
947 792 313528910
930 88 378668739
929 689 391895001
69 392 787715737
684 67 391342894
623 170 688562024
825 156 351248298
506 769 682246690
826 652 88002642
7 648 395999521
177 411 352107677
108 728 509055927
198 300 350740713
378 648 137233597
282 563 865840455
563 474 157413879
94 296 724992522
457 562 991473889
243 616 976505568
24 721 173493373
963 430 213982186
481 410 858577896
381 489 767347775
5 718 722013334
77 635 750260215
453 779 283719967
596 984 160583881
647 513 758336609
332 70 558181513
594 595 514207731
370 981 275768874
452 293 244457567
548 110 343943647
372 353 835015219
30 509 677709176
738 896 77974103
746 625 344613715
419 115 514354682
291 654 718358764
150 55 764828708
756 335 92249643
764 258 917863843
710 274 669833091
198 568 137144308
81 941 383271122
335 81 747265191
414 476 846046673
964 718 333517771
804 906 363690302
571 290 150469273
234 774 118840536
635 483 937670962
137 475 556424070
565 216 339788218
2 157 835108041
487 112 679986526
571 892 725959711
655 460 620313186
994 509 391734022
577 138 424608738
976 617 665797059
167 489 115328450
798 434 551348107
192 870 495654285
171 72 464964235
801 887 391097809
248 438 101336613
692 135 477410722
884 993 800343140
691 774 267891759
926 834 110357333
388 777 483194330
628 970 325254521
287 229 658360886
64 178 20714189
845 640 521077652
512 675 885164254
704 460 185141337
962 926 676019267
558 441 677783675
749 882 127999466
678 274 143700733
484 991 647140989
452 914 478975101
572 217 10079854
927 408 687155499
367 62 9892405
682 544 881998142
930 350 666899659
101 297 944561161
758 345 733457544
933 517 989415256
361 849 685424854
707 400 161233161
59 987 147332353
776 482 389208510
567 716 514371519
37 249 37738968
169 614 695903231
394 235 482266015
483 986 19490306
116 143 165502552
704 604 738091067
610 613 528487167
597 119 934791604
821 444 881707804
243 616 224691297
38 554 361377763
776 28 14340515
14 667 419910933
519 787 431234495
313 983 574439696
979 939 650481437
288 132 694374774
928 634 816787560
644 393 634196614
194 747 873506687
304 517 153302542
995 55 118065022
338 241 269431508
503 333 569549242
71 44 175700577
290 802 244168942
861 68 194565566
932 109 608308013
569 372 800192180
377 889 583655725
845 522 27275123
544 833 105543151
89 325 398766297
235 915 344148817
634 31 404473354
331 57 835370347
499 323 422932225
569 890 344518229
616 82 972222838
897 542 45131169
621 223 478427416
512 952 19064178
959 791 950013622
568 147 622111286
471 963 208614622
324 184 553355492
105 974 462471886
945 420 704287036
252 235 266165203
871 129 985512263
22 240 661032863
264 183 962876883
6 803 718994187
714 258 186802191
466 183 929928226
608 706 731680386
878 504 129044725
147 287 120018351
164 572 839842728
261 218 684166228
375 683 5051612
428 3 94128348
566 219 577443577
199 555 143469459
239 922 728181772
679 640 91639075
767 806 640112703
264 871 291300308
653 768 608051127
494 313 903432767
974 295 172313821
494 3 158901016
362 54 610628431
824 10 228064302
56 570 943454111
955 905 678852304
717 202 948823278
410 701 857775637
617 319 773190816
901 340 95024103
467 488 565332272
605 433 834855167
829 478 486540676
778 136 396300650
295 754 198017664
428 729 112170219
622 260 952434269
376 564 280427444
845 679 123095136
492 143 738628647
259 58 743260374
409 647 534962535
483 52 856977500
326 688 683158880
156 610 67149576
506 637 904584235
908 381 487889013
143 57 83657787
904 13 280054134
858 124 577552157
204 148 62880881
589 840 677083334
804 549 194714578
456 980 838076531
712 522 941860483
846 766 908551204
507 369 505677007
740 931 409584813
862 865 288524014
898 479 255961492
266 706 236349226
635 762 263612627
789 680 957673785
582 183 706801978
354 780 559377215
892 818 776492460
588 75 486771710
35 717 290983263
771 581 864197499
218 269 179031187
564 226 14830094
173 371 944181020
586 33 859963445
272 507 853647082
552 777 254779934
488 174 81587916
971 476 676870594
891 435 234942462
426 374 141272170
575 912 497512869
723 873 676747188
716 605 95413929
301 395 993793922
38 463 468157151
985 296 979229928
804 44 432080585
164 441 707444734
303 294 141041099
340 880 962895226
930 44 115925505
743 197 725359800
382 734 204098889
199 531 602537603
292 946 608687855
232 637 565339060
364 527 205935114
656 409 664736847
438 471 399573009
617 677 711020948
172 519 230704944
186 764 638469904
196 338 945504291
764 111 236962855
425 715 831106264
317 358 338952081
668 460 70854191
259 513 231797217
282 742 739033871
349 189 987045494
770 291 446754524
924 793 922164147
307 417 467618046
179 657 851402474
701 120 241193793
421 745 584064937
93 633 229349966
436 724 421606056
846 995 237690135
292 625 713609277
353 756 238592007
70 94 915689153
146 491 151228713
442 11 65245791
190 677 623428747
405 755 106225802
555 832 689732374
622 35 722613674
845 337 726813742
399 386 964100613
970 119 995108708
206 782 439580626
526 201 616824805
397 543 572341327
754 944 971424901
856 464 877819703
813 2 272149272
524 565 957029565
941 334 111384400
360 862 742397099
796 492 176995862
364 357 566727421
120 747 466257846
230 669 571050765
264 757 995444508
747 349 109878370
679 82 987403454
669 552 907474302
922 239 834663623
410 299 246058188
663 307 769336406
555 561 722898380
297 948 271847223
199 281 412561139
449 179 415052853
693 357 179880000
294 638 312336612
537 366 681176295
775 224 153912775
871 264 321178284
309 817 302981778
231 584 815681341
33 921 634442178
114 632 377056085
55 671 569809814
790 546 642246185
794 448 438656294
390 46 345367692
697 686 510655592
922 417 103898918
612 40 80417201
359 197 759901269
315 839 799916694
23 252 766967294
911 155 698195494
500 901 249970971
153 201 373156471
894 971 411499791
931 915 577069317
434 637 775385423
652 9 665870696
158 771 661059843
94 39 432455038
308 60 1601320
223 609 332146024
530 874 910114179
777 309 994984795
996 79 724295164
85 951 60009030
405 384 437670198
759 127 894276978
340 454 362890401
385 272 134318411
525 77 626147513
18 97 765736770
269 617 83688317
851 6 635170302
797 505 936195864
571 943 124123598
416 553 182768492
384 742 219460566
414 707 72730722
740 137 451810269
135 625 209058277
167 593 894224123
485 958 908925522
809 972 407036986
420 331 52383151
394 886 465151434
976 801 270343843
752 580 534050749
934 277 572069426
529 261 277808901
832 814 317970003
802 6 921424806
116 733 320914332
905 550 45210919
290 950 489060184
716 605 617153667
1 985 410830732
339 989 169978704
313 95 302372121
48 421 22701810
714 315 661164871
238 3 545446379
154 813 992378883
642 280 641836365
827 917 574241028
118 153 339412440
394 765 569374765
29 521 526256030
510 674 575249742
863 533 485267986
4 405 90921199
265 61 200011397
358 191 877730792
188 332 650765164
607 582 730143158
132 68 398791220
303 294 949675947
109 482 21899242
455 474 790503704
966 582 967011846
5 847 596920258
570 815 295633235
360 594 701558443
278 350 818125467
743 349 18678616
391 866 833760968
468 623 489919458
984 122 955064515
466 183 821313182
666 348 162002736
245 574 642090885
165 823 589581411
743 37 261367936
688 991 163790720
83 774 664583275
67 996 44401206
337 567 478537575
489 746 654522067
60 36 28351834
122 583 390930494
296 270 988416334
562 265 262634932
243 716 937174783
494 633 552817876
390 414 592621269
279 196 966840689
267 362 913627321
567 243 783388624
910 415 622961593
190 319 599269194
315 969 503500687
925 241 292388051
538 694 338101978
573 451 233252785
660 867 727887008
432 310 722836089
399 443 768807961
412 329 53689819
247 884 979662122
597 218 852812834
956 911 72881539
648 374 752091445
745 465 7759776
966 298 604605857
210 359 988086416
808 590 90749257
751 624 573343383
619 72 343610309
642 177 468799538
22 598 225258976
643 30 963406146
334 631 622618304
988 248 174659263
400 975 626882951
366 371 146510416
900 74 58810343
127 956 380976810
634 488 996230322
839 259 228571085
507 272 773602694
447 617 91188351
453 720 907081307
471 963 257365127
275 495 551869976
116 653 734446885
740 955 409190833
775 43 744099235
944 153 339563284
276 162 118177659
702 321 174679000
424 169 492906198
698 857 316468879
77 635 972006168
479 188 468404294
121 977 213222203
941 493 607668139
246 92 660646290
47 586 444084894
9 35 142298897
367 726 257331793
588 501 894347649
286 395 645634522
232 498 548447627
715 863 257121066
527 603 958902981
627 715 464058653
655 558 593832404
305 836 128985016
727 354 406756759
493 631 466344530
999 561 766720394
791 18 40653716
734 932 34613980
699 401 297978194
185 443 846869956
838 930 283141435
722 476 5013909
68 739 455664102
104 909 464741013
564 186 479024417
51 131 341663156
83 51 200573412
279 256 593498293
113 339 258372691
604 100 224251142
828 621 642620487
5 134 915223686
972 427 993810517
454 465 209894718
563 729 583453441
483 279 539549879
700 200 908249622
386 800 729038462
542 704 789833326
932 109 97511183
641 341 952450623
160 444 319400586
742 755 237772285
2 162 3076874
406 77 876644866
429 918 367317046
256 696 293071838
586 294 351989609
21 188 283696176
929 358 947433984
530 179 136521963
689 582 119615571
189 317 202002328
131 195 315955478
664 358 246291305
163 556 215543203
482 251 624217730
287 229 784714993
269 617 585942929
841 335 623241874
849 656 865233537
464 227 258583390
694 408 63915603
611 849 222383863
164 238 346618646
874 932 948522978
996 822 810486582
629 658 460767215
761 730 389413066
49 512 646915686
313 705 339995739
905 740 414183199
240 209 721744324
867 143 462604630
28 148 861451194
801 887 853016528
420 507 968332752
637 41 124113178
1000 673 345952814
96 292 776833187
47 443 209993407
155 127 386786378
443 862 952147709
454 812 221976817
205 838 782120034
378 300 420964988
881 571 140924724
941 603 70826965
498 320 998097535
349 665 430840667
166 848 812485112
95 686 487057570
852 851 76177917
71 672 964609956
725 760 804977457
952 208 644936449
343 412 472053009
188 590 888665179
249 197 516037642
450 310 635956679
833 860 914501992
91 253 721759940
328 741 919227589
8 46 787555747
315 714 723884855
902 781 413218821
260 652 680293456
923 382 665082280
971 698 377308061
668 558 489053571
879 862 89764491
377 679 725458209
412 541 169810983
866 514 948174345
461 825 318762909
365 667 157342002
599 19 278761753
360 595 726521057
103 84 583268982
803 851 267830108
938 794 797420346
387 864 124910112
909 440 994584077
266 706 287006805
782 942 442227197
891 50 174206489
123 928 981824534
22 336 897933916
950 415 617774052
589 305 594906425
968 477 69244872
514 29 435688287
442 768 171790356
491 596 776387545
850 79 173854347
206 480 666330375
941 168 70312890
547 982 863640211
11 487 171223351
876 327 116997390
923 782 600051999
981 845 813863529
627 41 43451165
581 915 401591138
391 514 747389488
320 247 557696699
81 933 753684664
835 592 740293370
674 987 821609203
357 257 344464451
692 499 561800985
253 62 83437305
10 758 478609736
729 960 43493513
819 997 343459711
90 466 283703073
602 1000 462276065
998 192 811685534
25 153 980838692
197 481 506569187
898 270 187069470
957 381 823839271
244 250 978559913
890 868 965438626
770 928 863872649
159 483 557495898
401 814 915178174
793 769 101493906
282 661 95210045
283 751 429359557
609 114 130310053
750 275 135687785
786 792 276015733
759 650 557308364
146 85 142844273
214 212 218224439
30 531 400898680
557 364 357502161
782 211 74883610
210 221 695217290
557 222 309105505
865 687 802334934
735 138 265531638
709 303 307087933
811 507 819225426
50 980 555663184
828 149 922999783
748 88 358382414
960 856 11030779
419 54 326171585
495 185 524781987
685 932 258596949
336 155 18036878
272 420 218025271
692 96 982522442
305 86 719947547
263 573 830804683
247 506 816529544
19 617 175875018
3 934 675821709
260 220 751778358
299 639 530257007
675 208 605193217
937 64 590977005
229 302 429157433
973 900 58627568
944 854 160919632
525 584 198023039
484 54 52156278
633 934 286555943
977 396 37827064
908 946 119984579
367 351 402517231
319 599 989405484
657 645 545256093
297 956 306780030
518 779 81062134
626 725 2030347
716 712 660278354
743 203 342550129
970 597 282591411
911 907 987424622
154 228 53793943
620 585 296922719
959 955 831021490
598 15 548466522
638 601 74477818
222 890 64090048
601 271 960828628
914 293 334885388
178 221 850574569
877 599 882722027
903 472 59177225
253 32 195297579
910 541 629532131
431 500 189931487
473 867 898059318
694 937 131201134
183 592 336572978
346 163 651692317
360 47 500535836
968 477 951479196
555 989 410659942
491 72 501290399
54 615 519449019
133 101 69826783
560 824 494783051
525 790 384897182
568 147 670437736
521 340 657231001
625 135 940136417
363 790 776451624
28 172 370238950
618 498 159495557
526 446 352812686
995 807 696513539
607 234 9991431
580 972 844071536
851 943 756875542
548 645 219793194
236 471 901244420
872 130 527504024
990 386 541036650
359 203 357047915
55 996 696727489
31 651 410923232
789 541 694458365
207 926 149936261
751 636 95890127
100 591 258106052
281 17 850957548
17 538 338332065
614 418 907911092
943 510 989804090
914 37 575989000
915 753 820299833
66 273 156352122
270 39 630104506
92 949 866467482
202 440 137047283
185 386 378676840
778 622 376892981
813 154 190960064
918 181 240152785
562 900 887103679
573 843 522886643
743 452 62191182
379 22 763655352
948 759 343137848
462 56 923636557
757 582 342177504
161 145 274077213
225 474 102611438
158 724 93040202
549 205 373238480
336 956 450885242
581 65 730304256
831 238 275809326
538 17 46379847
686 95 804250467
57 844 634164398
799 234 260890208
233 607 486056777
660 733 351422495
352 872 487655792
460 591 565172234
124 858 175017535
783 128 668142430
700 780 536390713
403 693 408533488
528 393 418888369
814 281 541922294
915 436 250741804
713 745 625953525
529 269 545906173
710 840 25596662
28 457 714083570
895 32 263952205
205 748 624905047
875 96 227742174
22 336 420896006
875 49 722727851
701 213 667817296
567 370 829910817
49 692 913013462
874 206 596313181
333 41 732871029
573 417 125240509
243 377 75508654
89 511 852721330
837 931 340097652
318 519 542548760
924 425 551172382
842 222 32449995
119 560 28110703
278 385 579349478
312 71 535212075
942 548 620762122
718 699 708105497
869 34 274845630
834 151 460865754
249 210 896411888
804 312 917766752
695 925 321251185
558 755 18611106
595 772 751308433
841 890 702278688
210 242 382874005
79 815 811163549
870 179 801979162
450 553 528893407
505 624 388796708
136 260 735681295
411 710 714775861
72 596 107386943
72 833 271127028
463 551 588337202
631 933 610919035
594 595 59217945
936 31 374591622
849 315 395855792
84 103 32508950
663 478 251294854
120 213 79052077
865 216 360764123
192 998 967560091
909 532 242364772
592 962 469047445
403 919 561039022
523 684 305870433
558 742 668416427
903 117 509400132
934 355 743366654
274 504 909379290
878 642 97429931
216 879 792833421
920 524 791339834
172 562 368805634
332 794 878635636
658 540 399455791
244 541 591598082
812 123 779757393
248 116 163805593
333 924 368247442
806 518 304438940
426 43 295447654
89 73 584816441
191 871 47238016
646 97 906293031
540 629 36728732
837 181 789667310
202 440 576056674
61 162 949987782
559 477 980854729
449 530 150263225
983 107 416154364
447 597 733266803
612 656 352226794
870 535 430121724
328 630 300100175
1 885 954381427
38 83 395290898
200 404 305235176
631 502 250099511
468 690 680147771
822 150 838166230
970 119 963542049
517 139 851054744
283 161 353582680
988 916 323356277
571 415 561656182
275 536 296932140
285 795 791378184
670 271 974507734
715 479 283080464
167 517 482417516
521 816 399671720
226 511 176786757
137 740 60180703
428 856 303983995
134 937 433709119
626 720 386524810
421 123 877675366
847 160 9925445
515 591 354460553
241 702 768045060
326 463 577564425
42 485 508437919
289 216 337022852
823 894 618743940
350 979 311594809
722 398 951882956
997 574 851540589
203 293 822302353
561 531 858190926
321 279 792659145
814 281 28487018
268 532 885164620
173 660 31717207
768 173 900079159
254 421 968446566
21 898 1485774
495 750 391047278
209 907 324053139
264 90 86991183
787 744 401129718
3 494 146636156
77 45 3681881
909 268 920304637
154 744 399556353
481 299 518396614
207 233 37021426
982 797 478862122
898 985 586469030
557 569 184527458
908 625 507031572
467 123 288347786
217 661 710027756
791 18 924179661
259 76 913006146
256 321 257583310
651 458 331547660
511 255 148192809
560 229 431910911
854 944 122407538
967 855 828334719
379 240 975291118
204 685 989493518
255 98 342800566
321 279 488834569
20 24 849490792
91 32 673456244
477 311 128614372
710 411 638302775
537 60 549421583
396 299 821513239
394 346 785837781
773 589 407978622
228 2 160099783
673 752 102969508
428 856 751123971
784 215 594721511
477 562 602331681
449 870 65668345
284 342 788727379
25 526 948861858
405 579 675685851
779 20 549902212
328 997 77276142
524 566 466279048
68 638 572693726
364 919 883908273
913 144 453076105
825 1 241869255
807 469 929193063
262 851 73853789
414 722 759346057
833 738 560321447
989 999 680429225
392 99 903602195
593 908 629366502
409 969 639983885
462 523 370017888
866 439 485211531
444 221 450525127
407 419 587873076
1 39 607114600
605 522 514725060
229 970 757839509
986 231 988303465
472 846 779392932
792 124 834329745
63 879 88627162
450 310 754321507
33 303 875049717
720 518 40168542
127 22 825993295
170 472 158224931
194 352 58962287
480 206 161889918
906 804 403786225
288 861 516847197
104 9 291260838
500 454 300546273
343 818 291066974
490 55 221651227
296 347 433581215
273 967 333825485
297 133 34126782
608 328 980350407
736 311 914825476
352 121 286346829
682 896 680521218
164 960 481601024
996 55 950327802
547 505 482858015
975 398 169099513
927 809 993550049
221 242 545010689
678 111 909652222
37 821 911772861
808 314 572220865
190 269 115412156
709 33 663562987
632 42 470293988
536 289 490513018
430 350 154390020
680 621 443831137
600 472 976021059
380 494 288848368
343 853 945866418
227 428 522594426
787 74 552838613
453 24 441178024
599 447 876240549
521 500 412189002
306 510 69545940
709 80 459701676
110 645 924712384
731 207 297725311
534 563 345526035
847 937 749518294
53 638 835771330
806 102 570637216
633 697 220218649
466 130 292383103
399 185 250095248
242 176 328519176
832 408 862360717
820 307 243982512
3 934 642749459
672 429 829893510
156 351 305366955
980 198 898455605
928 31 140771193
78 689 857468438
730 515 558910245
473 992 365447362
705 93 295338332
423 193 760235197
279 338 491083502
162 172 31921127
189 299 433472558
136 260 176563206
402 251 760263020
414 398 365904674
710 376 112310612
107 738 972025646
433 606 17891130
341 87 554265033
896 491 710199525
468 232 90184914
670 133 716012819
235 97 340751554
48 123 653368851
33 47 420025761
714 849 550210171
377 182 316373905
396 194 405712648
512 208 28925641
303 586 145320752
293 176 245978528
638 739 970973984
45 406 145848916
679 981 83567419
224 891 989297987
372 842 25348212
440 308 79111299
884 587 966379754
652 778 680391608
726 351 691990940
484 991 36250401
193 692 142683654
855 620 901156805
362 54 544597167
200 346 789428816
866 368 387789309
383 752 630271630
762 525 267232578
475 905 998443252
669 47 306817209
15 240 899692804
618 690 41772176
223 828 917536356
577 568 345458545
226 180 568220944
81 528 197027768
248 811 948624360
27 727 654895757
827 409 519827172
567 522 514659609
797 459 496328561
708 30 8264565
486 209 344097357
147 138 887956618
739 53 298235698
629 137 522254072
766 903 395383419
375 187 272543311
774 83 413956024
55 79 567264910
166 732 653815440
502 334 728868736
687 63 934876666
376 878 29500828
893 799 165091559
352 373 781713569
540 672 694584993
754 76 274566411
932 211 815678427
596 984 530666034
75 263 75052774
583 145 661919801
235 97 669112497
494 934 898611578
465 356 164126002
191 871 326877985
863 793 590204159
359 37 677585116
244 343 956878785
302 824 795031316
270 461 989229903
391 813 512401350
505 171 865531936
800 940 267501562
382 480 111089377
522 377 32651976
781 670 467700516
837 475 812669391
452 293 264996872
515 819 5143337
583 283 241493204
63 47 788589418
840 773 245679234
10 229 360993556
297 784 442589815
913 343 64891475
677 19 295465979
775 378 416685349
609 149 77316743
558 897 999753597
973 28 811016393
413 626 526960891
880 521 60158276
111 376 724716366
676 27 428578989
433 66 598794452
696 695 998623413
86 642 689675883
323 167 614559354
212 363 45096676
883 462 813040301
696 241 740869894
510 306 361896911
456 577 261864481
417 263 840564709
224 980 452117546
404 346 808236569
580 526 454175889
828 250 263611216
30 113 868944248
985 885 559864946
433 698 34804522
257 364 989185981
41 247 937195813
272 988 971476281
460 574 596786715
591 542 443001196
824 138 791643883
65 436 165431518
323 593 839056389
853 828 46543504
119 877 12929507
920 524 735995634
441 455 272498935
439 813 717897907
348 136 528238211
26 14 544110660
213 665 494629357
719 410 79785822
508 783 605042494
927 555 876573705
96 908 818516768
559 482 531891584
586 33 103012133
610 613 940741254
939 549 521266679
546 651 300979021
827 656 115548810
175 959 280691896
355 380 163377458
587 498 42622180
184 644 83923381
879 185 15380796
728 52 168827116
167 711 36699388
665 396 33379852
646 404 676381859
535 942 276371759
271 861 648923969
282 441 26990355
562 900 552258628
533 330 51055024
526 752 966551945
286 395 923377855
431 745 318086859
118 25 245176314
746 499 704916057
965 691 904209004
253 24 529410301
440 532 509406812
737 961 121114334
612 315 491170389
661 225 202210950
265 61 986857867
15 649 176890702
658 540 105148955
921 805 408875121
683 375 799747950
980 224 130144549
32 610 734002923
312 785 811165362
679 981 199302077
588 843 804922935
362 84 657147972
306 725 783694143
149 12 550639404
721 767 34622376
468 690 179189303
100 897 426916598
466 962 523302967
591 730 639187248
413 767 935718688
269 677 486975533
211 923 263965789
187 700 369408494
800 862 466958887
951 619 279714509
356 123 77488313
805 47 150209986
178 937 147564748
707 46 165808921
59 262 705938469
724 235 491948259
568 7 565945846
994 1000 277548065
135 935 595387651
246 526 714899410
174 936 418616219
460 574 970177116
32 470 998631652
497 682 623761292
574 668 337118563
721 810 242286129
390 641 666959884
696 108 316767016
996 67 9110512
761 704 42033076
868 334 262203076
121 90 741801422
331 236 661994163
886 375 809746103
44 939 130324277
362 263 560139643
167 96 424002429
692 423 664752419
409 647 327714540
858 786 460201036
849 611 695866298
236 272 781657461
2 162 791518798
713 254 725761758
686 934 874276163
752 99 570926760
753 97 828481124
615 126 841747931
355 3 840404526
332 21 378350311
9 909 602144404
827 839 542841640
250 223 446766801
409 611 938706732
112 653 867787243
632 364 965464534
728 52 753230300
677 877 358669921
374 795 644258048
176 160 389967384
439 514 282142984
552 33 208021533
198 300 984477350
163 676 8236996
694 5 46730303
375 883 559733469
85 491 579579456
250 412 514188357
948 902 591161694
961 59 974777558
448 590 798372484
214 291 377489120
316 529 625269658
591 704 273839953
459 797 59616928
42 609 431944184
81 933 587429534
242 444 716405971
859 277 369281702
593 193 89403109
238 859 457094933
174 291 839694901
887 976 721808804
470 613 560677230
134 452 460545539
422 239 356139155
975 165 586728137
885 70 714500978
90 872 203494299
125 326 460327838
945 496 226731745
63 669 591374812
931 520 501095663
180 564 966342546
255 511 908077811
131 723 493799363
333 938 140568222
301 895 112324456
445 233 396847649
46 166 907808655
804 918 684561180
530 998 575770864
972 427 755945552
927 199 158644669
171 984 461318038
356 901 518273531
953 983 838964766
377 522 344705613
909 9 325946414
925 888 451550077
67 56 699138158
687 940 102371759
976 190 575449263
694 281 243372283
683 389 256582569
615 267 380703414
329 789 841029780
667 26 987941531
711 957 280519136
58 105 287179964
150 850 366601783
151 731 53048755
32 62 914287191
873 125 328928717
182 576 44609996
886 676 704377528
561 531 715405804
539 183 228960750
791 18 794477712
513 827 19967505
93 355 970568206
366 112 905838573
18 158 473807313
425 503 741860688
650 784 192613782
741 761 381562230
235 200 19419798
911 954 554792661
892 853 755740909
892 244 366272264
513 259 270050631
43 285 264567342
297 215 266112623
111 703 408742685
889 370 521587022
220 652 10586391
385 430 5918809
659 357 394544020
583 547 326559517
929 582 303787015
265 787 73180786
475 918 747747228
910 144 331022437
351 301 30087575
810 453 934040431
466 966 317496232
861 902 168724021
685 480 493203538
2 172 110553495
322 282 956120831
582 835 765008769
933 324 364887925
81 941 371933570
601 781 935035399
385 916 344331311
700 780 177410075
506 637 148240881
93 983 194081502
527 868 759734872
769 924 506172199
831 225 953357155
680 853 781952934
201 912 203035607
897 655 463746788
345 577 348778642
917 839 56731554
987 306 542564232
724 646 534356433
935 423 392281281
545 870 365894133
341 975 548817342
435 378 97801575
127 956 475271717
728 695 880196636
679 576 799229020
664 757 102205465
444 210 564862366
464 831 121870773
79 978 298451811
887 801 179158888
578 388 239415176
298 582 878657870
680 950 424563373
843 126 915085378
293 249 235281252
437 180 649959197
802 881 48928330
818 913 594863348
627 506 797246569
645 545 776503704
643 427 228172252
117 600 435963039
181 658 929668117
640 182 659011386
72 596 237092953
467 500 457079428
562 265 743638173
554 397 451273889
958 257 228202374
584 159 129870919
681 276 757387795
182 616 999380946
347 610 751833219
920 640 732532937
362 843 902580540
390 588 817168195
689 539 817996728
764 849 951095577
581 158 982398778
495 565 998183682
172 318 678216282
897 819 647942853
307 263 162567085
26 187 44844729
653 11 520087086
198 378 530763661
925 826 418534339
260 108 236172501
829 407 782649830
784 650 36487722
634 928 588716959
799 788 773858481
286 156 447548283
218 447 135594225
195 140 191509294
747 299 32615109
344 737 524136959
753 65 426442263
930 918 49315964
87 476 160050962
425 793 260232204
682 544 753108923
603 557 522737263
292 935 438972292
786 104 41360826
809 643 969594936
476 398 459876818
525 363 366900167
458 770 211017381
875 675 557954156
732 390 741575412
310 508 343646601
959 520 707264528
542 655 175070278
329 403 87994370
683 346 344562966
75 732 733897971
207 731 429841320
609 621 443347959
99 118 252385268
356 467 592971610
255 180 973912920
342 537 228237297
336 101 237865617
409 611 83933084
976 624 850073333
826 152 303403620
152 666 117744347
838 205 485178907
203 719 993131624
779 413 768835358
724 646 198335677
13 111 341386716
322 572 712364330
879 289 135326161
203 452 635777696
785 838 387221244
218 877 825540440
744 439 684117545
883 462 123162378
620 585 761736963
943 852 454816188
451 8 496422844
561 809 366104105
697 833 129212992
868 941 817959108
778 858 350665643
789 693 929659519
87 414 530547278
676 883 662466815
153 201 525408799
138 229 491799559
953 686 967918222
337 576 843737623
949 25 149580949
706 608 871762497
120 747 871724631
565 990 280419511
902 215 395649120
556 394 599765240
769 314 899386407
200 163 946780416
649 22 791414047
977 317 874077149
660 768 782081940
626 760 74640169
854 944 21829461
711 644 206628536
782 942 476453639
16 965 587252448
848 641 113460278
940 399 205282301
793 627 813605325
189 213 173146586
110 942 764458738
703 904 643292800
494 313 810913923
61 900 58973220
519 2 4088001
857 66 56470311
256 108 648063051
371 473 425404296
303 601 955173185
337 370 664045824
313 428 640000399
208 245 786845506
949 246 289373036
549 205 11339015
234 445 403603365
725 306 790592092
269 319 523886616
219 750 427943534
26 886 438664081
509 383 295856971
840 878 493693108
48 174 327159101
417 75 884378916
106 809 748216246
220 778 186903318
8 588 583967390
840 426 810259260
398 722 153133232
245 49 481726513
662 328 555790846
763 204 30421389
439 681 502158081
62 20 447102632
435 378 684639554
722 698 500806222
792 104 315612960
991 397 349567079
277 227 332597787
168 493 198386281
194 373 989420304
826 108 883885076
323 517 54916731
79 56 338049162
619 171 19535310
252 724 853523369
596 860 957660628
597 628 456353320
528 756 574945718
327 77 352643231
671 684 106056762
416 657 522734670
590 533 492579818
973 681 639751343
47 230 665078022
902 781 305521548
224 43 377608791
587 41 941633523
245 662 254625203
966 835 200532279
862 360 916054370
305 678 586370041
164 534 217448114
671 996 570562364
175 959 990636035
366 442 979543822
731 151 576557899
526 392 556445412
251 763 773208516
225 164 381021718
627 41 391506203
785 804 777035739
7 50 641046077
956 911 221646767
540 804 68727880
882 463 81041934
504 678 815421028
892 853 108941855
760 767 559832958
393 304 624142977
916 963 360306097
97 23 245755786
576 243 338233696
139 711 520155597
520 175 613914132
986 241 601848973
851 262 547037273
876 986 719039171
402 559 529277862
635 869 966466984
138 758 202308823
359 160 456892122
733 867 333521200
164 384 168500015
136 925 287143605
450 783 320198083
981 585 282346136
383 141 406706650
131 749 928356948
606 889 690923508
10 287 130427490
361 89 968217693
57 236 68655017
474 579 629692391
674 803 549524959
201 69 263507091
735 198 477674077
115 103 382587294
81 631 839176880
444 134 636011433
690 993 681686962
719 743 930816929
985 885 750702246
995 170 439667795
765 683 191471795
44 906 744473166
185 940 291649097
145 146 354179053
919 659 577496740
95 953 270299088
945 116 795599720
563 464 765879017
69 25 781792121
436 915 736787619
675 875 624614068
183 466 60907186
782 685 417043312
708 531 209982862
63 237 667704111
787 154 897709535
215 336 258049427
585 433 964822164
605 712 537812148
445 195 280442308
811 988 281674114
226 274 179301215
14 883 484749245
501 422 749759379
238 3 322437458
943 852 902246893
6 290 496023111
715 808 691154709
646 753 516516894
424 614 560738765
73 714 632344311
917 612 114675772
976 624 887088786
580 752 1646087
774 51 840691151
411 280 679457350
432 179 591657441
954 486 185856201
926 966 277928924
357 114 90708696
613 156 50707591
673 1000 283265777
499 423 424485
130 129 316456318
639 665 348463339
532 284 552225847
415 541 379658683
469 903 296473029
863 769 310003801
804 71 921485287
21 330 775780538
708 106 791248189
682 491 119349499
854 446 161104287
148 968 630951812
372 257 476517909
993 798 778049097
556 780 230243917
662 208 109962831
426 773 132745286
710 773 258320770
982 801 788550959
222 899 875434797
82 920 952581820
667 26 660010183
832 989 383148669
179 416 6337490
635 986 485297768
864 86 612186393
803 262 78954882
991 829 460458404
330 479 331439847
624 547 193939032
553 657 739027223
187 365 929493687
418 468 369787076
41 434 888226692
550 475 364444807
992 487 174999600
160 821 349811040
308 60 699386978
237 594 653288631
579 322 579892541
727 883 937210003
27 394 653122508
216 536 275685066
86 280 863725154
326 882 198641550
102 344 118959415
258 361 568334129
40 73 124554207
333 863 582657335
805 578 975550893
374 426 325550850
692 292 91140852
462 14 430769744
795 387 634668756
445 893 709203807
775 735 79267226
734 923 169996453
935 49 440480988
860 161 971326015
11 660 194727700
551 38 142160741
718 927 246987502
319 316 155930533
496 278 5865547
628 970 188643778
378 775 177221399
912 92 671934
528 502 432083967
584 77 598845776
678 274 753432523
861 739 19906751
969 917 932293453
322 384 775892458
531 927 231010460
899 841 402986158
401 17 525597922
549 44 893140180
817 586 623907934
26 815 69045038
606 605 458302076
488 48 767518837
787 157 221235750
505 283 547994077
208 630 390001481
726 91 668142797
42 527 265466645
863 590 137674923
766 623 729373831
211 923 735327256
15 911 376908886
978 995 183477837
894 273 335154765
869 214 365704710
676 389 68918312
80 709 184886961
611 325 33656413
587 618 51857548
780 886 145149074
516 347 770687883
470 286 537445769
815 490 526411467
129 929 683698825
976 316 641882216
525 876 449692627
772 360 808584008
471 811 892301053
654 214 585460782
958 12 99712919
148 265 380839117
312 918 843137571
580 602 434675134
410 359 814814941
812 713 830762484
530 179 940779624
249 178 925697629
118 246 843019587
622 947 736117566
946 49 244679237
145 833 490099756
997 741 241705080
475 837 304983110
325 513 119029387
884 320 399122624
639 349 747906860
588 922 750277904
957 323 609148264
952 266 683898616
907 649 68832271
368 514 54582572
408 964 533396263
373 121 496064475
929 664 692654083
816 431 152776800
128 432 990502451
978 490 533604400
449 110 356748084
71 658 688874683
478 484 523341758
367 253 983783363
36 268 79451010
944 69 305590432
118 427 368153381
163 404 809332932
327 45 203331562
630 741 709157875
884 418 432862753
507 945 96067910
368 901 461949202
110 874 389674351
654 651 360540628
414 732 240149563
494 313 429174427
74 681 265862434
415 892 26264259
35 532 437507458
755 4 320927444
830 315 179568020
737 803 552139948