1000
965 938 940637042
28 965 209654619
867 965 631063279
728 938 682904240
336 867 707711445
441 336 386676210
151 336 820003605
600 441 22541716
479 867 408446284
526 336 236172663
480 28 452000851
459 965 760467966
521 479 132916833
701 600 703812158
63 479 417994651
440 867 307515731
979 28 801559418
34 979 357767798
896 63 178896508
517 336 481535610
270 517 693190307
106 459 61669043
386 63 490976972
368 701 791871435
222 440 480581697
675 63 509964908
791 896 17427755
535 526 966324237
18 222 226241026
620 336 157662840
1000 535 433908347
509 368 91331714
279 517 623017565
382 965 818046864
72 368 916253371
713 620 95587674
533 791 121393489
725 521 521955288
337 979 849795734
150 382 508084325
702 979 398402028
176 368 977094964
595 279 779317732
629 938 829986152
716 336 599475037
31 368 589056481
71 441 281887579
866 459 862098738
779 368 421617933
50 1000 477805640
153 791 218673499
842 50 957176337
710 28 564788573
740 71 157221818
579 151 390093874
653 222 423116500
354 153 760727948
430 526 377520615
477 938 731431237
212 535 766021247
935 653 820278018
345 153 612470200
784 72 655862670
780 459 56179005
309 72 982306554
947 63 733774639
754 979 70849976
712 653 533338811
744 947 52755577
315 479 633794897
245 441 623595834
287 935 196482762
36 386 209717855
142 712 611193516
320 1000 802188106
760 710 295689344
696 320 966740461
19 866 652925709
589 509 28885305
429 368 985070337
805 459 169002598
964 176 349445919
664 675 192006782
799 780 703497954
828 653 529314777
421 620 614096099
39 71 490049012
47 106 19850130
855 36 105685416
685 713 983522970
243 509 126116267
294 828 461196732
795 222 787309485
111 50 832404387
9 28 776799531
369 791 224796375
823 744 136879778
92 754 761961083
427 63 407224702
872 828 207435715
621 479 944888180
191 479 460409567
148 702 492608185
689 309 432266436
820 629 735048156
708 791 22036827
874 716 474164357
873 517 435750774
140 595 574472701
425 744 791564120
824 701 326496602
378 713 474854549
606 713 948892991
781 148 551836015
113 781 139527604
492 708 667831068
514 140 265591516
323 620 933535339
165 140 398317897
442 820 128309947
32 323 958787924
53 378 456858235
195 421 536270082
76 50 193088835
385 779 549814748
497 165 354155590
407 579 338392532
257 740 332253632
515 245 935381825
587 685 43070771
166 514 861797643
84 526 520314894
759 947 545414177
455 378 493917102
605 606 730413120
552 455 47387268
715 759 469474543
992 515 955061660
38 935 137115366
328 725 644730855
612 28 845855032
573 710 390714719
804 421 200860555
403 378 66359396
649 521 91331241
410 867 654681887
424 587 626483413
660 535 336396308
730 517 223281973
695 649 243447884
370 345 650528594
465 855 95410626
884 713 538884046
672 689 338985918
21 165 897431386
827 672 678471479
307 84 18940280
184 606 204392311
246 148 301468469
254 725 97531293
782 781 467454953
970 713 94568720
96 759 686785457
659 779 722849521
739 191 905682884
889 672 742155521
516 795 325980958
448 315 445975349
900 96 272262947
327 294 768775467
392 516 886785147
402 780 265603694
283 823 521743583
93 795 367625963
785 716 724780341
73 477 242810992
101 713 441433235
519 828 194437616
556 93 749581659
703 479 924345628
387 703 245729143
494 759 520820944
622 612 35984565
835 740 668625232
890 730 568329136
667 354 160113943
950 715 282002929
87 782 293030372
787 715 85228811
351 184 344200619
548 873 573408996
423 370 440481541
281 672 222828321
542 36 948423729
233 345 198912048
846 519 704371975
221 191 812522545
634 612 669425084
613 87 951937525
197 425 317891745
416 497 374765864
849 459 505376651
561 140 123058609
875 407 917048004
115 351 948842055
796 799 564950413
69 96 55798049
286 672 316324361
149 874 44554401
285 494 399688862
250 328 132074292
543 605 377638375
357 53 207816743
495 197 889735532
530 72 565067871
905 320 328974505
192 403 778523355
576 824 634186137
980 416 357740275
426 369 743877769
525 315 234650485
798 31 118435198
346 327 943621088
364 34 302513151
51 222 542869356
772 866 566791531
282 212 786190396
637 509 977782236
289 964 551221896
404 410 365090827
885 744 835182264
405 351 992685033
45 525 937622993
379 716 134217156
218 535 525245973
888 405 628709324
422 254 891838248
344 212 491687433
472 979 4043057
886 279 341594340
411 402 965017817
574 53 659094759
220 47 101813321
966 965 668851398
52 947 400329682
550 472 191004183
117 307 942517193
296 52 828057142
224 550 673125938
207 111 608621686
353 492 83334313
487 728 257990230
452 696 958813724
188 192 133146645
532 369 153301433
570 192 735720171
669 250 97606450
329 532 551564551
597 385 877373983
504 740 146311596
902 426 504598019
446 197 207917856
213 294 952447187
414 701 967735837
498 514 457917226
768 113 619200589
196 149 321613087
588 712 43554035
832 494 533076892
644 282 398513320
181 874 403039736
155 875 410002192
751 768 752973043
968 96 440304882
610 195 476036615
99 667 852698683
705 176 644476296
876 866 848145456
910 345 397076752
238 140 601909429
237 52 696008065
925 780 263071363
75 328 17514587
544 106 948355549
500 968 390538152
158 233 290689437
396 117 418142647
91 212 699550641
316 279 528753535
457 634 315029877
454 886 689215055
209 270 335269965
104 713 614203627
707 416 137779975
399 425 731048407
553 644 60479552
632 589 45746850
395 805 537588906
727 702 952220941
483 364 283030768
830 634 134609893
722 782 922812719
891 1000 229961629
381 357 262529054
800 479 201036929
806 772 835266567
894 751 488587112
291 542 27140024
999 521 648262413
986 245 38051875
182 785 115863909
276 526 659905747
546 73 131939276
415 875 28352594
678 649 424249686
388 517 678691959
758 552 754033648
811 894 684832087
844 71 840152682
607 832 913398243
269 140 120307777
292 353 724489304
231 576 74769085
627 525 709258590
952 327 670829602
834 63 876627798
919 846 904195982
836 712 761249937
562 573 590546422
263 649 56998003
258 873 379665955
859 315 41044682
24 712 618449842
880 970 756670846
7 796 209468414
139 621 92308629
585 382 419716247
776 556 843505471
809 381 8439382
2 667 887175054
253 181 680106960
528 902 268305426
577 92 246022115
163 63 750790880
921 52 773870977
352 149 813957167
794 150 352346800
460 716 84660518
887 649 278754053
989 820 285090501
154 678 880594354
318 504 745216507
389 570 600806774
485 533 193864750
376 727 236121502
505 31 481216123
83 191 794590887
657 550 14688356
983 323 162245528
602 224 995792314
360 804 993736289
226 751 836984127
815 213 582785461
843 740 872995883
302 935 600527773
692 150 568764994
137 787 704544318
566 685 999640071
567 337 73759754
897 781 724518445
169 805 683196125
833 238 223127984
990 166 47771971
44 952 301924711
89 498 808761709
507 613 48078309
299 169 617018359
906 395 45696638
35 257 227664970
731 532 311634965
78 815 436157144
464 779 397157202
48 45 282623188
972 142 249591720
144 427 893161512
818 309 477994978
398 237 994565349
735 872 583904122
476 376 573816707
871 530 790772052
466 476 428389687
895 459 267389520
198 426 939911861
88 455 28463442
46 140 824226069
911 610 879434756
473 707 725828216
882 370 110645705
152 595 40082264
167 507 519782116
684 768 220102685
186 834 326208304
679 562 131561032
366 414 946658864
462 649 103373175
349 117 908002756
147 894 198632738
687 285 307606308
456 71 475904133
228 316 668591551
322 349 878498976
665 843 371718077
848 514 698602710
719 287 371049306
893 360 736079351
61 815 490015693
359 351 633665032
975 796 782996853
690 386 446330565
912 791 877221851
662 548 982731847
255 867 591368790
646 166 826243050
5 687 541165237
814 378 123008137
825 634 297338432
200 629 455205159
453 250 626178730
64 842 760651952
131 784 148075429
20 800 223754366
174 675 188845433
953 637 878627341
590 414 606449233
524 548 267044977
560 613 170550493
400 990 462315162
95 758 376943303
100 76 172271475
916 646 751209672
470 804 793740607
527 825 331981725
797 835 400465360
98 315 534602580
481 28 854992382
6 396 313117637
105 910 920845691
706 495 939664654
582 174 173079762
10 349 258062038
373 279 714431956
962 197 526351107
339 152 999088173
709 166 426658521
933 610 820821386
676 992 790913419
756 99 428180100
444 76 348455095
367 181 286565684
13 50 769795284
539 634 114291763
993 662 672121781
654 836 719677374
374 602 593154570
670 370 92504237
847 158 190593847
581 100 13606077
259 589 644396878
777 407 592592023
853 39 995113789
997 791 39145151
955 329 364285274
127 707 134966704
724 835 558493019
482 553 512656531
520 828 182389125
619 395 26909025
489 853 628531355
67 853 900284936
939 140 702993285
502 585 440049308
375 794 78608836
699 75 515028700
949 302 62410215
130 505 846616454
870 692 628944316
931 665 525734671
74 52 912377097
677 964 268641231
391 69 355044146
511 357 442083678
551 515 187341700
40 585 461693710
121 292 431858634
765 269 862207938
850 167 178389263
490 243 998898741
829 897 595095026
107 844 850805199
164 364 567435609
341 765 198907761
898 498 934342107
616 465 118313933
563 470 754779421
652 894 426467880
914 253 731906767
726 427 612301403
761 253 786616102
394 19 424530205
592 900 581361269
211 895 492067341
932 410 709415246
268 675 922861835
926 756 198164818
194 366 157851443
94 421 846282761
312 36 787906459
58 51 279709437
523 105 24331777
704 993 787661159
852 975 541045368
717 142 415596595
108 916 192811585
790 989 64221215
788 652 700965870
467 427 688062460
559 166 881072162
80 530 353859063
178 553 977259811
743 620 351013360
280 13 833524342
508 246 771728619
578 455 366073230
248 919 506198472
363 398 254505238
674 148 271468649
609 532 916646466
450 728 545949585
408 889 716795209
951 612 941394667
711 322 321443027
878 561 740746803
773 19 924302743
554 725 498564044
822 659 819503416
945 139 360745926
838 38 346486084
332 207 824134046
469 687 581421813
682 469 719931782
904 866 376867934
729 735 753627575
330 980 516657096
496 140 721304169
103 374 139845960
764 970 774218143
272 411 421878295
769 341 511291011
973 346 328771325
227 657 897216696
141 646 476211971
907 302 861470936
251 198 704045725
23 106 313549443
223 610 173072164
624 344 20183030
967 834 410223528
639 850 637068882
15 153 146356373
668 46 803325240
55 576 693797011
301 38 770218210
331 818 778644335
206 887 203989107
125 472 270822625
698 2 701367274
85 353 491814710
994 997 605719735
941 416 803322744
436 246 396886117
265 931 408960810
124 211 886763025
568 849 120166121
118 662 900607405
807 634 707005175
361 63 454699629
658 699 660361396
817 255 735406161
745 724 136130434
264 832 375030684
217 349 552014838
321 211 54452290
645 566 774929495
937 296 927079813
342 690 330268812
146 425 687703917
603 612 969721853
241 726 264464077
540 492 297726927
583 509 270973771
683 279 666836699
774 291 584389304
655 198 305902765
663 754 435548147
325 346 115270248
837 238 889972456
17 158 693639335
54 935 47398680
297 652 833044455
963 23 277990196
189 233 442089868
334 394 440047609
862 875 513483592
319 906 394266248
12 844 362967357
62 146 841929317
431 698 408579155
371 634 334272926
478 415 109772082
697 907 980349275
976 855 506988157
49 297 102300244
435 517 269276362
30 702 941261033
927 807 988047396
333 667 241826601
572 935 578063186
720 344 785061524
700 363 47059388
892 702 184199546
946 411 786740762
845 509 279496921
961 209 921023299
434 665 344081176
235 366 38514033
324 34 463793926
335 238 495643727
210 5 461262305
518 907 725886985
343 228 627878458
180 220 509235212
631 7 178200874
65 333 261535857
313 811 932939724
801 726 693258659
79 692 641868672
647 385 903653198
33 167 422881124
310 65 408699690
397 32 503766884
433 697 546707580
686 376 580835332
208 99 740643140
680 186 679384005
239 339 671074839
688 182 615033526
940 779 925346185
591 680 29087278
267 169 489548010
948 953 290131050
3 108 560026177
626 408 264930706
584 902 738234559
260 343 835235499
512 312 254783345
537 544 688524149
393 233 338370298
205 705 61830608
120 315 403000398
428 375 346106327
513 897 566347365
77 692 456543376
59 435 697474884
959 676 67504233
960 744 557824235
733 421 890845784
860 117 300486927
991 283 281110976
168 791 877630059
934 35 350932131
22 703 667891554
304 281 744992054
737 98 170308186
930 914 351410721
204 874 732370543
694 47 684137708
783 849 461705485
789 483 280885292
741 592 383714399
123 436 841903249
484 21 585462170
666 530 923786631
26 307 582309605
57 489 772078231
215 75 320929435
419 833 338873430
418 108 697704778
865 795 709343723
856 88 465871413
571 502 569623493
861 825 479968775
883 85 850131811
633 363 277258835
340 680 349662369
831 932 307339368
506 682 263992794
293 907 825279575
234 769 457663822
854 727 872596172
877 361 423386580
236 489 359926067
917 817 716223554
721 883 178279647
826 147 547187092
244 255 600684964
642 379 585055553
136 530 419272090
615 2 425891062
985 524 284164219
138 198 806739465
70 772 244372166
792 609 905833145
317 344 837469190
536 223 938506310
575 13 608877543
808 537 12207334
723 955 579135786
755 791 117109897
187 761 423505379
4 797 762300597
177 652 510176024
112 637 88501722
252 404 1877989
977 3 417575521
1 833 428752235
300 553 971597380
271 255 910764369
752 500 157691166
56 271 185061892
439 791 293683182
451 705 283585602
295 435 688106749
868 282 984679697
617 343 997059945
841 95 569165600
763 728 627355131
628 67 129614959
812 571 620357226
14 806 627485926
438 139 9227869
134 237 735064395
114 70 412857207
643 785 76662646
503 1 938934548
598 632 404212067
458 127 805290313
417 832 211667955
162 544 352955208
86 289 100377925
978 94 359382206
753 965 420339534
816 248 358261925
714 745 915226876
734 708 141690850
201 435 28538343
384 333 446893398
691 626 404541537
129 677 795790671
913 784 219753135
956 930 983429961
651 477 267352034
274 837 73406519
266 294 214900234
557 612 48724468
256 318 631498526
718 931 669553798
355 84 824123247
126 279 115593512
447 384 205958229
29 236 432028370
549 568 624946736
857 669 187315288
135 566 173162218
762 874 354004715
996 470 509879152
593 912 342742150
618 723 138327410
608 77 16703261
819 615 720750077
171 705 623514865
987 304 743513265
746 886 260932483
179 402 873379622
16 556 507934310
449 856 1686847
565 537 662793897
569 718 615553278
81 731 174259417
611 758 939201159
486 526 530534399
160 511 956943200
390 905 13751009
90 779 964621890
928 127 688778587
957 411 866314061
803 231 200510867
974 246 543813273
771 765 578058711
109 928 598986047
775 607 498277134
214 83 551117328
750 811 144408547
493 315 556884601
326 382 411071534
901 484 856718112
145 387 70917094
25 867 67901640
488 497 447230417
377 339 691000764
242 844 812877097
810 31 603375993
908 466 76278500
474 556 257489356
229 769 84565305
681 819 83161585
757 622 723685004
157 548 488863631
170 428 42245826
461 376 86526378
594 820 848607880
409 710 193991304
102 762 44894306
288 560 721392030
314 107 549667903
97 908 771174204
43 672 820627814
463 25 901520524
8 167 186965016
766 328 876885730
786 876 698072111
971 431 603765120
813 243 758084055
673 319 944709249
66 168 631800214
923 167 826623427
538 956 701586840
958 363 109167822
641 645 68713437
936 88 54746957
175 207 928880434
942 168 677762319
110 976 386649732
68 5 671359271
190 597 199757901
586 789 709428754
11 617 286017383
580 346 34994394
736 987 961425900
522 271 849086893
183 947 88332271
41 682 64351725
240 363 43146432
995 874 882205810
499 326 676621877
338 634 395592222
640 171 892365626
858 735 266851052
650 11 39849661
401 361 252751648
475 195 411213459
230 952 121394779
821 324 539766097
596 480 316227588
749 149 973072339
232 294 513796091
899 403 342782331
156 244 47037908
277 442 245917199
954 610 261966516
273 61 328268069
648 573 549383461
262 88 877955715
748 514 280235848
311 861 414445410
132 244 388372837
468 14 486399832
420 317 456459084
308 785 24819064
693 455 127565274
60 899 739223057
840 523 408581500
984 609 760797985
863 640 624063759
305 231 825896707
432 617 600613263
671 784 215057314
770 25 332913969
732 867 867007463
358 285 976736253
219 402 367180856
922 913 294691144
924 279 582681809
601 794 533799854
661 893 914267129
42 153 970860067
216 369 258884807
545 456 496081565
969 554 121187160
656 827 515725958
903 30 689718671
202 295 402949937
981 969 612008049
445 746 535642212
742 341 714597397
380 42 437719655
116 285 724439339
491 528 433383558
767 925 671994854
564 205 39300009
599 207 462535177
851 98 898635655
501 167 578315948
944 474 442211755
793 615 116421878
261 165 834521087
471 761 699859165
943 77 673871711
529 221 35255741
298 289 870934131
278 890 109106011
747 743 384959540
27 513 20146963
406 977 305291225
193 69 926170711
638 293 342302716
534 566 32481374
119 422 316628551
247 252 767380568
555 504 173427959
541 124 228586845
443 827 71776050
547 698 764994530
531 487 857486062
173 500 293880619
290 566 31457267
630 842 895607733
614 784 409189356
604 809 62592984
558 689 54091271
839 332 808029807
203 660 74521253
303 611 594692939
869 684 412340299
372 682 601221572
159 698 795644574
199 699 135526175
909 305 679587677
982 497 576494184
802 250 433855783
225 953 634916961
778 588 743846410
988 574 569348312
635 938 418006356
636 899 558486396
437 153 875531212
122 156 790305821
172 687 938292282
284 92 948373900
864 396 317426958
306 670 655609325
347 593 456326070
143 496 182403105
915 266 694419577
348 678 550970893
879 377 505165321
356 661 444353896
275 268 228611547
82 906 244383618
920 187 111915493
998 154 84930413
350 299 242396954
362 596 276486628
383 919 545754634
738 753 820269131
128 26 343429903
623 107 60048228
412 915 540019319
365 222 595604332
625 98 971980570
37 675 897466078
133 390 715370549
929 640 831357530
161 770 321537844
249 951 587764168
918 500 639353773
881 38 590115690
185 99 266193650
413 788 74786427
510 421 371865217