1000
517 961 332405975
418 517 349450023
817 961 2984676
261 961 784231986
670 817 459794075
934 817 753096596
611 817 534329467
321 934 821726851
194 321 913934687
458 321 491308543
623 670 152442960
130 611 858012178
486 817 90901808
38 321 767636784
414 623 218873355
761 934 248022508
884 414 260956214
291 321 60041383
421 884 560779581
440 291 366619558
487 440 401957858
638 486 286998454
534 130 747262320
545 884 578307441
993 961 777411341
973 458 969956199
748 261 719453889
159 748 932820057
244 623 211606930
802 261 290825435
610 159 664239797
513 517 827200431
766 545 928541252
399 993 83455433
580 244 534830579
667 291 90254461
989 817 597557836
639 766 869534735
745 414 55134557
737 761 111171881
136 321 612587012
864 440 755533315
621 802 498999450
64 961 382941004
193 761 751981151
215 761 460440564
435 38 422578873
17 611 421404235
34 130 836057829
445 194 573481375
845 130 581360025
70 64 321219041
794 38 798981571
396 421 367798231
144 639 360805668
966 610 23949388
617 667 543119831
717 458 697956679
507 617 649793799
769 638 251376578
58 717 377480562
420 517 714558800
312 435 56483632
428 766 57445258
701 421 172810831
210 621 38765830
988 611 772748068
115 507 238306421
442 988 681021761
529 973 707995049
879 435 305907904
835 136 953939253
237 144 265678828
738 617 916226958
255 445 379088677
375 159 341881119
273 611 505182205
148 617 669454459
581 194 773760834
732 210 678287533
962 34 196099443
351 748 620705985
183 136 546280078
474 623 226936041
873 399 937153071
305 144 754133635
574 802 712122263
282 639 791455267
179 144 526152716
154 621 931313821
832 237 619926000
856 973 794991528
651 534 995968904
746 442 513192618
71 130 848187851
238 418 69742365
664 237 813666828
633 115 45074690
765 255 83009630
356 534 759949368
822 545 538711961
299 664 852826531
771 356 252200418
289 244 801008942
180 832 15357808
522 737 192744823
227 574 641124868
323 966 523677787
171 323 355698952
942 746 339986820
930 835 633745468
387 130 850977787
437 237 476353554
808 387 906854862
121 244 520024408
167 179 673862974
949 474 562653122
168 183 478462065
870 154 376608564
823 154 709839648
292 522 752878428
366 823 209818894
202 737 843296213
925 193 864338164
521 737 82778271
598 664 662622274
249 387 318585277
94 183 548046534
59 823 721304289
941 442 211494022
156 144 613277289
325 513 97437808
590 941 104784825
267 130 79018552
230 884 849475562
657 144 687112253
714 292 155975700
473 581 747427049
406 667 947333680
97 611 596404261
750 70 227810557
181 227 453797865
770 115 546146905
416 770 567943436
212 144 993560537
454 521 548727859
394 261 628726352
7 227 207730279
162 949 335441936
296 507 74962816
744 864 118528633
565 387 668213747
259 59 837929003
662 249 622756880
205 745 191650750
839 121 304361707
174 737 516347408
841 610 851253859
854 212 952635559
871 97 869223630
715 623 273315307
642 70 3435920
152 808 641804259
426 305 931828313
479 856 708054534
891 394 334329614
527 738 998968290
777 136 327083622
285 479 636964475
607 387 117848249
992 808 411365350
488 406 902042320
641 973 920615005
549 930 701228621
140 488 335963715
929 212 346441348
353 140 55949956
907 623 609129567
612 823 971204713
530 841 274805270
813 993 795539095
728 154 289880429
405 670 178812861
129 962 22219338
77 479 670553010
425 746 890024951
719 748 164870576
44 426 459103406
340 802 615361854
906 617 965845505
596 808 91960060
128 925 478465823
251 530 806123017
185 428 809818857
407 244 92908523
784 425 850144753
516 835 379328477
848 715 322671049
311 194 912912878
342 770 407743906
535 574 862588192
608 611 13541242
678 845 14916011
397 574 523464726
30 802 190451638
811 479 412086613
711 942 90587909
998 421 198089065
709 988 708698934
695 442 693499555
298 822 448092220
591 152 502980795
15 766 727891380
221 941 313409797
163 802 780758238
50 711 928512758
93 670 978850312
462 641 790634614
724 420 272812817
981 737 309706792
256 185 757170141
886 934 452211374
531 144 504149632
89 375 777543965
757 642 260075231
690 662 910496033
430 638 551420395
595 925 489564462
463 822 459224421
16 770 146830591
339 437 131928161
881 152 948069998
200 77 89054919
189 406 56932854
532 7 212283422
634 595 943722386
916 521 972335337
68 353 957820845
92 421 694556493
602 639 527067794
26 709 967323483
231 633 482135089
42 881 294637743
123 581 936092868
833 848 248249139
578 291 995943164
390 578 675328773
751 356 994185352
245 366 428759280
957 474 896668241
95 26 371294275
276 339 12574210
666 237 771356746
493 210 287255551
503 462 137392876
449 42 418774767
57 507 153018465
653 171 704414641
564 493 22709789
354 442 663047981
867 934 719696512
926 745 457089932
27 210 327306156
630 714 645380169
411 396 546622540
209 249 673961497
330 180 98504827
498 416 573461950
122 396 130682768
775 406 179585857
137 608 75028899
876 664 929609373
759 534 398629193
614 595 664904961
367 802 340959764
127 653 689880564
838 612 526212876
892 748 414113744
928 867 81429216
684 549 339665525
484 405 229258478
805 527 917765120
927 534 467666041
177 437 361367355
280 454 363830632
262 276 866258287
222 879 228836484
899 748 101652911
982 394 717612468
45 653 983852805
160 411 574425838
579 856 655934403
755 458 977501353
78 761 457777218
589 292 892922774
855 848 494223032
468 642 516170134
514 7 316831473
669 529 851880405
253 891 85650661
971 982 404466310
279 238 995951160
349 669 313456682
82 130 54648147
377 64 966146779
294 534 286604232
559 590 719449166
461 559 22989648
955 276 612354865
964 50 794423959
175 715 341332865
85 684 332652743
138 189 996748792
553 463 809338235
643 841 222670372
626 746 759723092
65 17 955514109
800 394 667431230
80 642 205726559
277 435 255393789
96 998 203523932
659 724 313750524
157 876 527785306
795 473 932781020
116 82 81600215
319 349 756508647
890 659 973434200
698 662 570838123
649 738 262827970
186 724 933613390
460 479 256185279
481 137 801443404
75 928 689502801
558 449 406179330
66 58 115255855
381 487 392407140
901 390 697739806
302 70 275327963
81 670 722492011
772 449 194818969
315 927 652944962
552 70 721249558
348 765 939174494
878 876 343829130
851 770 79829396
217 769 703168974
785 261 663749455
39 623 160150903
98 418 857591073
796 973 567724218
502 215 792928926
41 193 648717743
169 279 16676619
609 253 690930943
799 68 290820771
475 405 261447551
648 66 834214576
241 901 294614895
48 321 862772722
576 621 41667486
937 127 384153617
931 129 910149222
142 481 794480075
105 48 447644658
597 349 611497295
975 937 321614102
258 530 618634496
827 437 638979119
932 152 394935723
36 633 732989424
704 891 402887955
56 302 868800628
561 294 761058796
768 634 523970180
410 892 305419606
965 871 487201841
297 502 779793455
645 901 400065050
306 755 781912432
226 626 686056966
712 183 719206738
924 244 793499307
161 651 984452716
810 901 767002636
384 161 433478256
478 777 263632904
178 342 675821133
950 177 986516900
271 17 264598072
62 698 774623168
875 580 406037062
789 202 443247612
307 237 940476759
660 115 850286036
885 181 690605211
939 189 661075638
278 552 841437513
544 273 749668068
774 377 963009319
73 822 386825105
919 85 528361462
151 521 746696874
401 719 87901540
661 802 682231194
229 553 561094929
494 854 409991015
631 885 89258048
557 140 36807227
786 38 720263474
866 998 52618594
556 237 239904347
247 98 729518319
88 715 906570237
616 751 616696935
149 527 800003080
888 144 159693305
675 823 325823158
506 375 406124431
10 817 645337175
629 238 329370589
382 175 249095243
79 552 231567999
983 445 729967753
615 794 13827622
935 926 605738015
972 659 85936057
287 311 325400086
893 291 330306268
360 629 282034622
216 972 746930895
970 642 386168358
234 36 577617159
268 772 36180687
409 616 847719340
555 579 85513837
11 581 167390684
575 800 816642015
584 493 86355711
636 950 391379484
754 179 53879796
22 287 107467852
99 598 544610547
192 425 182147242
260 649 423029328
383 229 495141436
731 282 323213370
936 397 991575546
374 340 705411398
852 670 167006663
680 961 577893520
985 516 827169306
341 690 98551904
350 503 959153400
681 183 699367314
710 68 219753099
112 291 956561976
252 503 855065614
753 555 686171504
211 827 27500874
288 564 159395529
5 189 124679341
654 157 551198672
220 96 12519331
632 473 54431239
400 975 214729549
69 130 931481581
392 44 179073236
863 552 386213379
587 425 165610488
603 294 27607226
110 93 160011728
427 564 400037939
327 927 250629225
842 578 299231162
862 795 302889001
132 353 951982634
19 795 854090707
391 421 779484116
592 215 143870664
206 384 952237894
819 670 508765613
172 698 228829003
528 714 195709629
542 770 379580536
812 878 717133886
968 611 839629625
524 639 495965621
563 462 956338853
476 267 702562304
707 808 762583552
601 484 585102609
485 202 762402938
441 230 107284913
850 178 773021912
170 142 528421850
219 186 162491117
143 397 22144528
586 878 288516667
593 85 246302927
821 777 931701415
84 972 555326481
525 421 461098911
404 230 257070211
21 81 550626374
758 475 254899304
818 227 1339319
29 5 47266156
857 955 638304662
472 110 850887012
147 808 429854215
987 851 999677630
310 418 850056872
109 178 86312025
131 428 549969121
797 777 698288096
536 724 158053935
780 823 126358896
483 575 639964284
540 942 954073295
417 662 409646920
674 494 231890186
747 710 392448621
683 777 235966762
436 888 597836618
702 517 76959558
846 683 24287877
419 530 287241955
120 319 619773635
477 160 237018915
55 838 605111188
336 11 342797362
379 442 188397804
47 785 932171134
370 885 272697795
541 227 443041869
91 136 310072544
635 418 884059261
225 302 273189871
903 966 908436308
482 879 515453270
814 812 598844562
958 401 44111707
733 848 289810195
787 602 570297232
572 174 301211364
689 142 263096748
141 256 958850098
520 493 543590844
358 851 225698390
920 643 980493587
781 565 619156378
51 221 75956913
889 745 227185130
176 814 506539763
729 607 547726343
372 751 773038736
994 219 566700931
940 71 788390679
978 372 236780606
550 747 791865628
860 611 748455081
444 211 759057218
687 5 541255179
265 919 42549502
948 372 108077161
686 529 703320055
114 130 10873853
329 698 503450114
943 461 410546755
938 670 261569103
14 151 10144964
671 747 750718184
763 212 675014259
269 866 935600374
604 744 50244025
600 245 456867761
829 58 506357978
4 130 305153122
716 595 313354823
432 934 317366532
697 710 467063595
254 78 294363142
214 876 314962935
318 445 689332965
67 514 452619546
909 65 373863397
723 664 879225493
182 478 761203473
655 850 786021679
195 789 521729717
508 41 483334451
466 817 289567372
317 285 942045747
25 516 790260880
945 863 3717095
164 36 432621989
912 25 706023123
692 949 915464022
158 890 535065205
117 441 635323021
408 488 426753027
668 312 600190910
917 216 721917131
519 182 83514960
825 875 46471705
284 680 609296336
23 532 73303318
749 420 737337764
913 284 726183887
570 964 986557049
567 761 68839523
720 312 320221054
352 601 532628643
515 774 130110126
865 482 371075012
456 964 84558542
153 445 5179728
395 686 73605682
984 366 745474017
726 62 385910024
790 442 832373094
364 400 709566182
371 50 291695320
235 704 655983528
424 400 867064363
324 445 602430407
740 258 238450115
286 298 857073543
46 829 300716450
389 215 825496507
322 167 127042041
995 99 582934553
334 709 956235340
263 82 243662514
125 680 351645724
504 811 709170775
512 123 595968498
204 131 868899907
471 93 742405939
696 787 213638609
736 524 464093329
703 486 796542506
844 521 2909326
490 65 935979578
548 616 792028904
566 561 847453040
951 123 878242073
90 252 940421264
274 925 180489923
335 966 568940147
694 282 73491301
452 550 280270729
605 394 663564634
423 716 909526864
135 193 560258051
86 209 193688535
368 540 829116831
741 29 341990675
248 399 73660128
826 4 55504654
74 38 555956282
969 796 95498214
111 733 811519888
779 488 30535538
403 516 255839508
236 487 355900391
53 194 708516527
963 356 201604187
165 70 808904893
918 426 104897635
355 715 724018263
708 175 226520093
554 531 920150400
872 440 74600539
979 4 646258750
467 466 73083193
538 737 163444252
921 479 315585248
523 315 411709773
895 312 26316012
537 851 80709310
264 754 640246008
622 870 8176519
618 391 738566420
880 684 339588051
3 92 187209210
628 144 338486691
207 758 60904005
792 273 367299144
373 729 866333577
464 444 116064414
868 787 881860993
361 251 922106069
752 467 796519739
788 341 794869235
882 425 653436192
539 565 642658184
380 256 934711255
313 217 183572411
126 319 100151960
239 962 38504062
727 564 192732331
338 704 151540235
359 67 810464392
583 148 707250089
807 597 421108124
627 659 181152761
606 171 869202266
499 404 868190216
809 719 807545126
429 795 865332094
119 958 446433330
37 135 660637784
190 161 939967292
199 589 362422119
106 151 156120049
413 119 214488615
304 854 217342997
431 90 627253921
496 587 555170769
944 535 250457176
688 717 379340761
722 711 494976101
739 268 501765420
640 417 258100768
345 138 140537171
320 961 158565441
266 989 357958553
250 812 68088201
203 441 483229027
197 544 447599804
594 278 772927313
213 142 175614571
834 458 435192662
533 471 823671545
300 638 298554134
734 140 113781435
1000 250 415268435
599 129 72879520
242 727 63031315
831 432 63428178
218 429 800882699
665 848 582469924
849 966 200131640
33 541 104871609
422 204 705473609
571 499 570101663
902 931 297713305
791 919 618027902
510 643 335354064
776 399 840489928
146 845 106212110
270 384 627666874
18 194 123365595
663 667 511729285
730 522 893072360
853 269 786796893
824 639 125297752
433 430 335551534
952 242 580186986
793 609 986125341
347 341 840238915
303 476 534449679
619 648 575339600
139 581 200223159
272 541 25417537
198 70 950327916
83 98 878411418
953 794 289977908
804 236 523362931
415 916 406134745
547 749 568506323
224 473 495255212
898 341 774790638
767 194 806303078
677 148 561300308
201 789 712577246
947 427 216459375
705 995 652066455
459 565 206599315
650 167 707647589
63 917 484278053
124 696 810042640
883 422 258829438
166 793 480249098
453 350 348134702
316 157 872764311
439 603 622858966
102 668 627225420
897 811 18450232
762 381 705832259
469 427 534313771
412 862 248925510
32 971 823213689
682 130 309686317
447 407 907626562
620 940 995862755
986 740 164924690
240 761 157155589
369 125 707231275
679 622 859175692
837 649 229856553
764 578 803690915
43 945 134464192
997 416 959273822
87 435 148586788
24 958 996922123
861 953 251306176
760 258 895864078
782 920 798916210
362 241 724235637
511 541 356290334
1 661 108970394
959 120 915211600
526 709 315850197
457 601 399600645
859 95 322282
40 442 762802059
326 111 418620037
923 737 710484022
773 633 749868698
551 200 857498966
742 258 64012509
134 528 164881520
290 432 416136101
365 95 927046462
500 732 917159962
398 636 144660965
816 595 945150300
208 482 613656579
900 205 726572722
960 694 386724139
783 146 84421575
363 307 269853604
914 540 427523177
337 667 395890305
991 586 35756475
118 208 639358119
9 872 190448461
815 958 138273635
699 661 178551674
735 238 843090543
908 969 501875924
543 27 894598371
676 962 26547060
104 866 551671075
573 456 404734279
495 596 361294640
107 927 786399334
840 78 360819064
61 280 398449826
446 687 54076198
31 575 222410310
569 424 261839697
869 508 363026201
386 61 446708744
672 381 761004996
451 785 697862459
233 968 705372021
691 94 728635870
103 533 613081749
489 230 113253557
803 50 108608525
501 755 427423248
492 682 955812067
402 698 30692594
721 849 227530913
658 769 887623222
652 912 235738659
980 489 225780906
894 7 994187014
331 909 157618850
956 711 241857583
228 997 308104861
301 968 72974919
378 607 916572290
20 947 419515837
582 147 431881353
13 823 581228250
624 773 528433590
54 487 248144134
293 940 351730141
173 517 862666204
505 435 363258533
967 78 204099409
49 19 746978369
343 899 994259557
438 270 848808418
874 217 305779733
344 703 201921529
8 965 380204286
434 297 714835054
743 478 304723941
546 201 986467826
847 342 227889956
999 618 119131213
904 326 785992875
101 885 166154993
283 743 542787246
706 864 384413058
196 968 545212084
843 538 907044754
915 123 783688913
577 347 671158119
295 846 107510406
184 927 970220163
28 215 626240811
72 4 618770586
332 203 618995989
801 478 951719925
798 129 57924142
12 299 506793023
308 214 717590273
718 819 111947727
191 655 182095408
388 660 498457851
996 115 617333588
385 681 153148715
637 212 885714035
756 47 88207850
281 505 109721859
155 206 140490748
560 329 900483128
625 235 663362937
646 40 105651187
713 924 63860375
910 151 921615775
328 280 175037431
76 351 621719108
448 879 257455774
187 403 544374589
933 604 777625368
588 855 285244168
357 733 809693872
275 144 397449565
100 442 451005398
896 228 753608588
568 677 845202799
877 475 762873216
828 242 734982126
52 665 916196363
647 984 133496691
990 748 196638660
613 555 70702206
133 485 892345070
333 111 836903279
243 992 981133017
976 605 831142313
232 849 649692114
246 960 259058644
518 155 966302434
113 854 984595742
6 538 571981967
188 566 410209064
778 668 881215303
922 604 199230223
685 928 782651825
806 425 155831897
450 186 855323555
585 878 136747311
946 963 934028539
858 752 438036386
693 190 643572241
257 918 546778149
562 405 424491551
150 440 756618041
145 702 540504579
455 587 588507728
725 838 126160230
491 544 88128619
644 147 295466924
836 567 370491449
830 44 64676401
480 539 263297767
346 714 317764798
887 585 501258681
905 321 669166278
2 427 832235650
470 43 610163771
509 726 793025855
954 380 981111632
223 829 270151947
376 628 788726723
911 931 336743435
35 26 986639679
465 857 258842188
700 690 249793997
974 955 984036641
673 353 165411561
443 142 465627253
108 595 181078175
60 131 491131738
393 715 811801579
977 454 670759986
309 418 689660847
820 841 285687890
314 480 941506402
497 159 365244325
656 964 16794294