1000
293 963 737030364
207 963 179541713
203 963 641640693
320 203 928550370
230 203 133567848
440 293 703071800
481 320 14651820
767 230 589189851
458 207 306892473
312 293 440578014
281 963 106099488
901 320 844540734
597 963 546378540
67 312 15118921
260 203 226405828
238 440 767456595
916 238 766447290
709 901 63946391
950 238 710275588
47 320 37662305
69 709 105168352
9 312 329188733
887 67 915126161
472 458 833827015
170 69 543548263
616 320 268846552
211 616 14545632
713 293 730739391
857 293 812175606
592 616 60143386
462 207 986903948
806 312 299428370
674 47 527816344
782 312 949317367
347 481 120285393
632 782 174632636
506 230 361631896
753 713 168677513
535 238 352935329
76 782 325585697
666 462 631259136
756 506 128569027
112 347 221802315
783 472 8814239
445 666 916464290
22 9 750496668
925 458 935116429
902 472 351093570
2 312 104964808
415 916 973434411
354 666 499079090
540 230 99554613
835 47 391720161
89 666 795208754
588 506 359095798
930 592 723178978
590 540 69638448
962 590 819160000
678 962 128119438
977 925 83450014
459 47 374842207
829 445 505352812
538 481 561960616
574 458 256270248
904 238 244541152
610 312 216386475
733 238 604222857
862 887 545300944
479 347 98884726
247 207 118885780
788 674 445819764
843 538 30347768
841 458 599059402
328 806 474143492
36 733 275623710
402 440 788296027
850 588 100007074
672 402 126478336
227 678 954755989
521 67 574385027
697 590 533006575
965 767 360927000
831 415 169441563
470 925 227984212
40 9 826453779
246 112 177710438
310 977 115214442
658 320 206591654
555 767 680466329
872 666 173841101
639 89 37754876
95 260 963151466
400 247 765529282
622 538 2524259
79 22 752270308
202 713 709502591
679 211 486928115
432 767 411843160
233 2 481880329
365 227 620697176
399 458 244043182
126 247 271913974
245 415 489126539
960 354 259412099
769 733 791743208
363 733 970464917
117 963 152062681
237 806 995614687
387 247 390949825
812 672 927206785
486 281 4951641
77 365 4311794
83 574 189897896
765 399 469653154
274 831 439699597
525 901 597134835
840 274 81853760
155 470 924296835
875 862 195672663
815 930 683647905
304 916 702454870
287 841 252056205
66 674 252288743
939 479 575988476
51 387 66687126
919 230 992420521
600 902 860118454
455 783 579881421
101 622 647665782
716 765 546581732
428 238 437589273
8 765 994869704
914 472 236611147
971 455 719151214
382 462 4282787
160 756 450686024
72 806 182444146
158 481 401687641
797 521 97595636
115 462 466843711
566 733 564066676
131 713 57706831
896 363 447673283
292 753 411279303
867 733 589500303
362 713 878674902
267 835 724722898
446 481 202642842
575 95 49208527
923 486 253565837
348 843 540636457
421 432 19099638
947 538 24887640
892 402 442523959
721 203 827262739
533 238 3592574
906 126 905386282
785 470 225774635
917 486 417496813
376 610 48856471
186 610 242741256
601 857 132686847
941 160 932225598
634 697 189546506
409 72 166322463
576 481 85290931
559 432 608883827
599 678 47584530
609 79 972778925
742 486 340371418
468 440 109452418
394 22 316685008
198 22 992052675
303 538 330068138
393 960 363327090
934 916 721588334
334 679 504865574
255 574 864703017
474 77 977900367
289 247 762873897
294 862 40420372
683 472 168922905
241 916 787466763
808 962 949805596
848 421 893627539
491 112 618927351
924 8 142900361
936 934 227903330
744 347 966594278
46 575 929486638
833 486 813610655
822 812 509835743
147 658 244376186
425 470 274367132
758 67 441116101
34 599 472810127
162 131 762150939
218 812 424632986
408 348 684617277
201 83 648103673
764 126 757827611
315 963 916396621
498 247 792042295
192 400 667225343
981 848 154776070
560 875 912954102
866 160 504268023
577 525 482981346
396 474 308812885
302 491 582763393
596 590 332693291
463 733 463349460
839 304 958778757
706 362 667280975
251 294 626020821
20 399 533690957
259 155 239692551
824 51 91751593
569 559 519441802
167 634 663714672
397 481 714706832
937 533 61458025
554 198 581096004
301 463 106640387
522 463 413213337
439 486 235637326
619 960 829956231
482 421 382234113
707 247 521343103
360 67 780477174
664 394 89134243
620 672 9784690
351 415 334746740
603 904 864835118
263 89 160210723
816 20 975941800
818 939 762561342
344 816 655971024
523 577 674316974
986 664 950392155
762 923 100331831
476 840 714039975
118 207 880846837
868 468 743213990
283 767 795222722
842 679 450240565
364 901 674187301
979 560 122273123
860 79 215885250
955 758 439350673
280 292 862088001
705 428 763711557
331 769 297473214
595 601 424681452
995 815 390435140
584 351 393432198
690 382 299165431
229 382 659605352
617 126 863949572
337 833 526362621
488 919 718640347
944 707 217218545
541 46 997492847
528 937 636360764
325 95 420004178
64 848 19748963
854 939 94874618
107 769 308346739
671 815 339684781
781 192 673335418
811 936 483779063
883 584 965243686
152 310 134136624
340 690 556808606
585 237 121167138
314 409 175949710
579 304 227605113
217 883 819024218
563 255 290051429
834 541 553000492
643 538 629987269
210 76 362877794
291 192 419024814
150 210 707374388
353 101 651163364
516 83 670836878
982 806 744933463
100 364 640215598
745 697 810683402
636 394 374534630
932 150 212502584
199 713 585515879
637 834 534831433
712 843 595527370
677 584 233258410
736 603 702162154
223 51 864814193
405 76 885218576
178 365 83446327
4 533 135771373
661 887 42303974
377 982 412564639
684 560 63488947
750 904 508999744
285 674 189351604
93 337 664977778
803 291 793511686
308 281 670421419
927 199 951546176
361 233 300730394
190 331 245970991
116 281 256654655
469 917 950998088
161 816 454450398
729 468 560966952
62 116 38275436
874 415 402692826
175 198 894722189
561 709 337615731
530 862 422332032
573 901 29164090
477 839 296459198
996 344 899166585
493 348 672883045
239 672 877371948
57 597 232949811
138 446 580085339
798 867 621939655
626 347 699899769
520 868 380176903
141 477 597362054
416 363 969903776
423 241 488142042
873 574 777162484
63 866 53489749
85 892 572943370
791 66 877744510
372 860 92916521
827 304 892509460
502 816 231469069
249 808 16770243
7 765 193755657
884 217 755588364
747 34 733321813
204 47 556414910
615 223 317541683
417 155 145149894
920 923 637518917
454 753 917278374
135 971 811745523
165 709 111401697
276 204 851093490
275 423 573016254
174 939 522154401
735 671 986849388
330 247 846918136
104 841 540464264
492 827 116985883
889 924 265046034
467 47 457316138
527 941 416937545
54 783 422389225
367 944 431392812
898 320 214586842
88 289 883990328
81 207 461300902
311 259 489610342
961 620 621257539
182 791 370785987
299 875 531430967
398 555 753047165
457 523 792787135
779 944 92840309
928 274 645387654
499 619 445814147
324 399 470061
49 72 641198024
719 294 735511570
749 916 949738682
821 634 627276865
724 376 939666576
316 364 952863491
355 218 248802832
17 211 281844460
741 904 124414338
130 919 134263223
500 302 335754305
612 89 466892610
503 423 836674579
715 850 150713875
652 423 214333270
773 522 554379288
478 107 693254360
999 294 626375047
306 117 634173379
326 396 37831741
787 36 275233645
496 425 252739787
10 747 187640592
200 705 389456157
407 348 667166945
480 960 291735415
433 480 771601608
228 365 397251927
746 769 984953059
959 387 19948107
403 428 496741276
623 263 648127391
589 76 287122228
254 211 149746682
321 555 641916822
687 773 529573876
565 95 958722301
951 831 929033645
288 839 264590726
717 829 813165745
90 573 700956012
208 658 352787355
882 4 331137448
593 211 833026864
134 344 124780754
243 590 667792185
784 175 653041788
547 472 769514751
424 479 381926583
153 937 145771961
629 961 270891302
775 480 274919947
606 593 783337902
179 204 279493277
926 500 479707862
151 340 81304981
562 301 106005078
270 769 301346079
19 719 497929676
726 245 765233173
177 20 392383948
869 584 375989704
710 639 374030944
205 211 349474991
127 205 755443469
653 920 985067269
660 241 895327255
272 211 568719433
169 784 76331838
725 928 603263322
271 523 278513563
976 840 912615670
358 4 768934578
124 54 159424967
703 615 666012178
532 606 914071242
907 951 553404531
557 882 670954043
180 784 122352220
338 311 363752412
855 615 72959127
146 541 218606648
148 446 953850433
940 843 901184379
613 907 684696855
524 237 789347865
886 962 344281685
953 787 312504997
625 664 756332258
890 202 366660962
184 117 940290201
406 816 52595590
640 606 929254846
795 454 827123212
414 230 621810924
42 251 292222752
183 620 145329364
65 955 969716942
374 541 472642882
187 977 342414682
164 725 75859121
59 521 172617881
543 223 244895538
123 705 922794907
738 134 616350752
708 779 116372974
556 533 379402725
12 827 830452293
974 407 65474871
770 923 967806969
84 595 234561445
564 433 785193039
760 382 416500861
114 480 117805063
176 126 860691826
278 361 193870945
870 521 297727445
173 306 644238370
992 54 34713424
154 377 555084915
410 470 889066031
693 161 274710245
494 259 335579852
994 746 887211625
570 104 84050909
954 211 605990649
1000 599 123256148
537 150 299055079
935 161 179474382
15 467 86189013
392 238 239465580
691 233 736355552
86 632 663539054
298 593 72583357
853 724 161909934
978 592 719522538
485 782 891011044
983 146 570544201
172 243 471519666
911 764 253250821
628 241 200161750
698 454 869800635
26 477 855449086
266 51 580628431
60 833 382142362
776 170 822298207
356 502 132746003
3 285 274367506
993 308 686390695
68 67 756547964
427 589 139138172
495 210 914626513
196 358 340598279
193 721 309943809
586 609 163739591
52 107 492288888
972 911 139178743
413 853 33786893
345 162 527693004
859 468 708768515
1 116 773285546
24 872 640991771
551 862 767278044
103 767 210198949
858 415 489118092
378 716 832768646
75 205 990029228
13 423 644724810
438 658 987894713
98 203 732725309
442 415 605720364
139 995 808938868
897 493 66462320
219 775 173436648
952 40 636235256
645 67 303483846
191 660 345012255
737 49 863820418
657 116 70229685
696 227 228894184
434 698 80933111
608 978 632579641
774 476 871172729
264 840 64508286
168 869 675547023
383 407 847996518
343 285 196870778
676 314 479324569
757 811 434449206
244 251 587846307
515 351 440027219
819 34 48288273
309 438 308102796
97 405 403390677
863 480 523168252
143 719 677517911
461 40 490482722
880 897 251263608
373 169 45754604
647 609 855228100
505 824 402331834
296 19 405844757
722 612 364706884
552 811 894478903
754 623 660967231
349 98 359675468
125 360 862390784
273 116 826348914
73 201 431441500
877 815 424647012
878 927 339745555
967 217 220569322
895 875 215914692
730 126 212878200
720 249 457912619
189 227 606731932
633 986 34553993
956 747 87703414
43 427 77926935
751 600 948098911
380 467 406749037
29 482 84066690
946 719 929166334
771 445 861486246
508 505 267628703
369 189 978382669
918 897 13999911
437 330 73394144
352 488 575178659
830 66 338335529
447 396 856050199
91 653 522847777
327 203 603375934
933 751 627551772
82 863 788722551
942 863 822842123
929 29 579623316
102 49 782083726
435 43 872368758
14 435 140189971
881 498 474572611
41 986 356576820
450 576 713647344
225 880 818409152
359 787 448913286
813 123 452835354
970 454 543809735
673 868 27592305
110 359 262991626
790 180 360316903
386 49 144947826
845 247 499415179
823 592 755322005
429 924 45813945
509 927 439223211
451 51 466166602
53 26 859042190
885 927 983553680
796 821 438492885
240 193 284514998
651 481 333341374
483 983 619602934
385 890 21512287
695 274 68662600
988 715 620711509
602 394 910657939
473 168 148787032
980 775 928957303
391 920 468217293
966 146 815936915
464 886 522340206
418 696 117919021
517 508 244698748
339 647 495115872
166 239 877902558
814 590 859555519
300 118 740715526
654 378 237036886
681 886 600831484
290 521 881508210
322 616 486163841
921 615 659566294
905 283 814393052
968 69 390907013
945 806 401401261
61 935 321029081
984 972 985134254
667 4 506644508
888 798 617511091
213 515 828416296
871 176 245902840
802 637 484616349
465 657 647508841
539 911 233616585
583 424 485030115
550 503 447028151
375 615 83082998
28 416 361334265
27 589 640113099
558 919 626411218
578 517 456094153
662 774 145974812
810 101 947996193
611 352 178250319
650 348 484883026
714 498 713261097
752 834 333714877
471 726 187112421
957 410 413229127
655 979 210486623
513 550 53996652
659 205 239826233
389 707 237715351
526 834 493517821
649 687 202328223
587 276 202094323
768 135 349546875
381 747 766622494
235 993 203392576
333 757 477472857
799 712 913422462
621 405 444341945
663 773 914079778
912 557 184381527
56 661 268422228
635 349 309640751
989 151 47958080
149 658 968980055
94 896 936453564
142 324 680107848
844 208 56954728
444 28 495756842
221 158 439106721
991 882 351970695
759 745 886853752
943 439 214681073
734 208 717933633
731 906 112788725
879 626 686135802
685 486 51086319
484 928 984136784
832 869 518417456
700 762 100021907
16 515 804744451
531 691 74944786
113 353 514572734
335 925 605064134
618 322 923442126
426 103 810561688
121 811 774177481
341 661 97327433
778 221 908750412
668 180 3431445
39 193 887734116
828 65 186601084
31 762 957061947
70 954 135784009
422 932 271089832
644 330 964465245
30 719 344153471
140 569 977882678
638 640 421180830
332 383 829072611
420 246 417601868
607 112 623391252
614 49 255279787
261 565 337649838
250 468 442940003
157 170 229080444
529 951 579389141
132 413 908504697
105 979 649284
258 255 635200612
800 468 218135721
646 842 254111028
682 579 39295637
772 498 279004198
475 857 426131125
216 930 704707974
865 896 449823803
388 474 503403288
490 532 869257203
489 737 388100893
990 783 874078685
136 464 435628426
460 902 828710367
188 63 801145618
582 796 997823261
805 294 849698215
453 693 263108795
197 790 144017221
282 560 776434910
987 310 441957401
631 254 794292680
544 984 836305765
727 475 703521755
449 707 957824733
329 339 518523230
820 492 177766552
109 989 998362747
548 558 777846650
732 957 106421782
368 499 496029395
688 83 406444154
390 577 336490845
448 392 488770787
371 117 391169069
185 392 281346509
269 813 481542804
441 390 872720194
836 400 766195125
985 829 38381223
903 363 140492128
80 746 266080287
536 952 687991567
641 889 397809027
497 971 621619717
740 278 186850979
137 643 394950869
861 584 385088061
297 15 139412308
728 509 576520270
807 555 233233944
801 935 499212476
305 340 92788213
838 82 88170921
222 446 925297833
48 267 865218665
71 926 512217767
969 867 13445044
412 326 449554877
856 639 182840507
145 929 130517878
231 816 316000056
58 632 710650655
106 537 396044138
401 324 462615819
268 868 872003725
581 101 355518830
452 180 526861380
702 800 603209651
44 904 159307006
958 706 917569542
786 79 566133745
748 150 815152990
553 437 128666892
33 870 316238825
826 91 963637420
404 177 816887045
675 19 256984495
279 637 565396003
45 467 211820448
11 58 441374797
37 275 656147194
6 538 808200909
899 858 417396443
627 141 94538165
948 954 843392533
234 358 919666134
605 389 799133314
209 693 417744812
510 668 997975575
975 309 362259979
789 577 395999298
507 351 734924152
642 873 554023438
18 219 645363240
92 803 821514114
998 258 373959031
545 806 495121489
119 371 348667481
99 28 200736986
55 613 31350390
366 127 127367570
794 554 698948985
248 462 178346058
669 140 140167785
849 937 360264039
680 264 960910063
96 712 108450815
913 762 177130921
630 768 383189375
704 579 745922979
973 977 549987355
817 628 171996799
876 203 474081954
598 878 385050266
804 941 161839062
518 869 914935282
571 728 386120744
319 715 325243852
701 608 357899353
699 391 296239893
411 251 629413833
711 773 235274866
847 767 63165958
370 742 709787964
909 578 597773017
780 352 549001425
25 70 359303493
514 901 122396857
111 48 574962434
336 645 506988566
436 217 802594429
689 354 157847995
594 4 58529666
846 202 507036953
50 775 427660367
793 889 236139391
226 530 547601088
487 824 326238199
38 9 424093749
572 17 75864742
257 596 537708257
763 715 885162717
777 312 34902096
350 450 631734950
120 631 507478280
512 168 530049313
419 403 555092764
568 348 974488453
922 210 786603780
825 520 199820984
931 410 664652598
253 363 247589037
466 972 489123646
313 706 748810898
212 928 312989092
252 750 397394133
323 988 450533474
915 778 662515437
908 170 442385243
224 544 876834193
567 461 589019295
286 660 129857915
430 861 362175441
256 190 690461667
534 71 163715700
32 963 613147414
604 933 413815301
624 782 143172963
181 417 550138533
357 822 436101081
851 684 902013256
159 239 461336285
78 592 333463956
133 477 321548181
35 290 52331256
694 154 131027935
894 882 90295794
766 652 447555764
215 186 922512742
171 240 118558674
74 477 230887834
265 572 711134088
23 419 994973568
156 50 992289058
122 338 55146520
837 218 458714549
809 324 908225079
443 65 785408517
262 924 166352047
938 733 668707381
665 675 424846398
504 493 661314405
743 499 188745946
214 480 34884728
431 889 688281964
346 827 366841548
755 624 110845169
997 165 983250004
195 404 934909289
277 716 790446392
964 477 332731836
546 348 811710681
723 161 861165462
949 537 822601
591 974 378559471
549 495 171911344
163 625 217172505
792 89 830441376
284 25 746528027
395 221 603629892
144 414 320620174
220 577 275762252
379 330 557487074
21 296 223866630
656 112 677466714
236 148 132072195
891 173 453446844
893 954 101831806
739 886 543974312
242 681 635716598
648 123 72304673
910 689 779255076
761 918 21022671
511 418 792046967
232 721 34730640
317 265 144100121
718 916 190215448
692 127 974009584
194 230 788163711
670 382 432404302
206 476 940273174
129 368 251114747
686 713 258050686
580 823 241902784
108 833 253498792
542 349 413796666
318 722 408242182
900 62 444829120
456 68 213813492
87 873 228332510
852 577 733590802
384 67 909258082
5 274 141032822
128 620 749822327
864 635 799270374
501 378 496604006
519 72 523984794
295 398 924650780
307 375 840810119
342 90 898709235