1000
551 406780425
138 212223059
1140 915604386
37 166452293
619 985242919
955 555624273
15 12069960
764 56106748
387 767726140
222 639825520
493 250886630
1086 321131820
366 782703853
187 224563245
554 84769357
357 79372525
1186 701766817
4 121883547
37 88569496
247 367108069
1077 783754737
29 313680824
986 384458073
806 799866203
955 65562515
1068 173098037
50 255671364
330 482679739
272 751224517
128 998063553
12 350371675
75 466197420
757 542140728
196 334385623
73 785929627
352 894815888
986 285440639
912 461683209
91 588545320
107 118716572
1088 959492345
262 615704269
317 135528181
465 401597019
78 942518333
153 116989896
961 557004793
620 448041918
591 264863494
942 987003803
878 73004495
483 390377640
1122 559216289
435 493586734
214 141348078
660 231152377
1105 951180245
242 922578044
985 611179597
727 607633434
94 102846804
597 198066911
750 114382991
756 295897611
98 814764962
872 670897886
13 732877494
832 199427564
421 31911557
915 73194357
414 927653960
1004 564071946
829 761584623
1157 34755815
883 290764028
813 164140396
425 687277673
128 885546242
22 725912042
1163 74355934
1116 87810818
633 293224178
1012 255623731
1147 32143742
90 375728314
94 399025291
295 505240367
924 831018696
469 595709291
917 926968082
6 83571223
213 652261407
614 539676218
1194 90397582
670 793212212
27 430791133
973 876998014
982 460812430
206 241518729
628 80345567
1145 23684655
65 668981116
1189 277058558
558 508895627
471 768469203
264 584134500
1181 314144528
927 8139109
493 917812710
638 188056895
247 803094520
574 745166867
389 693210059
501 462666182
902 956425306
813 88271087
474 714919474
1099 740008629
188 236195185
1116 997192205
740 143871243
148 66732959
150 145405370
272 561949135
838 938107116
12 597283891
168 352475168
1197 54047720
803 139931904
828 126354958
521 597686953
520 20811758
756 291862131
1096 322598916
351 791612577
528 71115622
1100 559187803
655 465274602
202 408735815
439 890152781
1000 694401323
401 802942439
498 74589175
771 590403876
1112 639319701
191 21177404
914 926012633
312 465760127
704 446108415
311 395256467
994 610675978
1074 779626000
638 276258666
685 51338696
214 169151306
86 124746032
875 830312673
1178 932347190
362 614766120
585 582986480
419 713688672
1142 117738628
764 199361197
764 100939169
725 12687430
182 606784753
280 166338182
206 745061857
10 386958655
294 15333919
198 371637175
833 805733417
568 851944621
406 178186334
901 901187518
888 138920406
213 274620055
358 607017083
1173 949212231
632 823161269
987 721815319
66 70998794
999 514924369
508 688002581
576 491992383
14 655989043
230 551486687
327 380996681
309 338188174
978 145278203
100 909215780
1036 608651709
1003 206462931
884 20949781
310 567617066
381 49754749
1017 90533024
761 846874667
624 780132868
1159 526178114
32 105217075
348 1674153
753 756903542
507 536943360
698 957710050
1164 446557195
1197 344583459
493 731732975
712 728817416
135 652578472
989 443227449
221 706893336
968 658291312
57 296491777
889 933965722
312 68883298
265 37883712
133 991137158
1059 914844302
911 759072543
112 7410281
1105 67997673
323 1581800
741 667616532
537 792389519
740 25661672
405 416884918
730 875858951
463 903585909
768 448352663
661 350204783
330 688092622
1131 574735854
975 13887534
583 212873114
389 503653591
270 906608705
896 417805907
105 516504572
893 62455093
15 762607901
1153 278755562
569 967615557
85 856113452
54 473712895
603 198697820
1143 98827069
148 577667391
261 991323682
656 67354215
714 695618669
1133 444426169
588 16448745
614 39981158
1028 977518922
401 698530747
58 138170826
323 738832163
646 457162217
207 993989575
52 456871100
359 740982044
259 604458783
771 949465548
825 717250597
845 54023764
952 141383737
267 880550069
289 711555903
593 37118110
903 701153822
809 992409966
154 623684620
1104 862346599
743 466219011
956 150974840
82 591263420
4 120900867
494 734418320
334 220197104
1188 54448284
1148 508071292
123 726908561
463 327262236
309 990726787
527 560231640
502 194126882
1023 920831096
301 303561914
591 538298603
536 75663702
236 257555265
678 550489196
62 307133599
10 252356457
1089 95384450
952 312746639
740 781912258
1136 499008873
604 260371359
1056 78849619
125 262992465
5 315732832
652 903003745
85 24086283
772 341265476
1109 273436422
642 581952386
1034 642330523
1107 725518556
972 292978663
421 79107004
259 354547044
1193 852645483
323 438115602
450 151145551
890 486701229
841 635703717
359 101965380
1068 808261137
1024 533000853
1015 304442214
856 930294933
110 44622333
708 470290041
354 449016326
664 6112420
754 103634742
102 508021986
433 318423068
1023 657600576
501 730337948
139 505985010
97 263890641
688 824144792
535 880326611
414 418756432
1019 994979240
975 672578534
228 272621521
317 517303187
231 728594891
816 960833434
869 577433832
16 628394799
435 712331994
832 786497029
166 10029655
841 376058590
242 729022770
277 955477639
246 337069901
1104 283678610
695 889660348
933 947727164
20 922518399
844 431178714
976 517784888
1017 47848229
485 103197997
161 4140755
500 491568394
274 144270292
502 199845553
318 804748434
1180 181796741
568 603877020
597 731981706
277 373058577
258 750498744
150 545916729
304 998341353
456 676223131
892 625711800
807 60781566
157 721937852
537 445212340
457 959031408
400 510607232
295 308804154
1169 867445388
842 845106662
237 836331969
989 361405681
956 554819558
1088 735712017
541 560648416
922 988209486
971 690341253
632 118967834
413 514697026
438 492330926
776 840064537
9 935510064
935 818356539
283 403931876
632 916551338
779 182162899
473 61030466
582 278592844
1126 558854789
663 701013659
1174 281849236
117 136070993
746 884715687
738 754613897
591 177466473
1195 326135676
541 666066600
489 619459281
1121 263177112
1059 187360767
702 460699948
589 364566055
510 450073800
876 641068483
2 338303430
1149 113773195
925 792066840
512 344842993
991 560586351
1000 917190802
753 199669585
740 119068414
664 707690601
703 927374902
139 697634187
195 75294780
648 858076335
461 693084449
210 256077919
168 445154527
1136 692056545
809 2596982
1165 183825294
719 732410255
768 357258670
1078 136997410
951 433737266
1020 360528238
1016 646932418
945 654607269
737 65882213
106 293079980
207 243651124
809 131105371
1094 875957361
1108 176326794
1199 517981546
462 742561617
163 71568249
931 254064108
198 61221264
892 957482119
612 500667304
957 916274533
47 305518971
436 256845249
862 599190490
1003 727312831
170 74261272
752 45959380
1104 252605642
520 659446282
816 66353499
1077 131037552
1003 316256189
462 675420713
921 948050854
694 311717995
76 817346222
896 955187418
1162 268128440
1087 592110224
1086 791032316
248 754254662
657 531483930
1198 908022504
243 154858899
64 932511242
946 595367176
289 29171337
1071 405847962
18 834563526
80 911494621
387 830513629
595 27707550
560 746601255
747 486308098
70 211237239
1181 314444606
850 227937394
541 543915610
417 305377364
1155 354463577
1109 755322002
789 60800040
9 811709359
507 229864117
687 689703845
642 94512772
1120 914777162
444 396054835
1092 709406980
672 264963648
977 896421178
71 522698867
300 879614163
708 28541269
407 466389044
211 125336836
800 364450571
377 126601940
659 47715160
716 396294929
1145 878849541
712 341442635
1099 847201917
940 785648776
729 144446091
634 885810359
979 298386942
470 746317517
583 657234267
383 227903723
911 205525765
1063 770931681
1196 298161725
829 506161537
884 424666968
1085 156403471
945 647514249
889 283223616
1058 365825699
678 108239640
822 96163123
312 942307087
1156 339375944
552 239731168
1060 501236314
533 300307035
53 74714788
20 885518746
1010 542939218
1041 575730949
194 748552932
330 315882867
376 953669680
302 917949394
115 794662986
893 245324221
663 972850134
842 198012494
697 2311676
119 548159902
853 693215105
206 39764290
535 603178062
604 677516858
396 185002194
1157 615052953
627 967679634
511 525270879
177 343391579
317 595843279
491 71249502
182 474292145
804 846286508
1025 780302812
199 108565599
1152 115628633
669 370912736
194 915308960
612 30358176
515 977971755
243 638596261
729 59123154
444 265066069
1063 475564630
476 143820235
687 745759590
1176 291461932
997 285142673
1016 650042191
906 78939518
693 801842711
718 642117829
189 576285673
328 273994708
1193 972428181
446 50060344
594 191993365
556 623353511
740 904556930
606 917102139
621 912180385
284 122764838
935 406419553
844 588551254
940 722411191
679 308909916
713 63582247
14 75530740
390 577581932
376 487137436
387 329839244
271 232785292
610 122854090
15 441429360
528 893468879
497 355006289
51 964507229
506 158541822
823 691830537
513 790901596
986 798145340
535 991930876
1079 811967733
122 27001689
75 717082010
667 851738904
192 185811008
811 779377586
1084 944017358
48 847930082
486 161347663
777 486741562
179 530699488
307 194170428
774 214524305
326 32029789
1116 305020568
1146 956300358
646 140138054
446 182317767
893 608150275
247 943933125
127 201029327
246 973898900
940 358723976
112 207587349
1083 220493176
996 760242681
652 359546220
332 637420688
400 474081733
159 618845299
1052 839209443
1023 206643583
587 98210109
1095 497978480
702 325374361
565 24140163
637 189685173
211 739077757
698 716535234
719 308152959
166 565379359
494 3067377
209 385119392
736 691072264
629 264435412
353 918189850
802 283368341
375 903500112
45 902057568
672 542410984
976 576864428
220 550506896
839 511661519
1190 63511577
959 318756772
587 276299255
860 726298999
673 975868901
644 835727998
4 744722962
208 735541064
190 396804653
1130 718438793
16 99265981
1136 908685203
516 393185569
1044 272293613
1171 598130059
28 48714585
194 774177393
999 627210679
822 353654963
1123 137203735
474 293418487
726 37087334
241 224084094
289 45286672
811 6995941
700 463529206
1148 945273647
587 10947100
1040 8298093
636 950588012
164 452895859
472 72103409
700 899670768
251 987747812
734 557170508
288 797840370
1188 8924331
201 683023129
639 317578106
54 319158647
123 720967390
1059 902098549
121 541687404
292 759062687
927 72298624
43 88723611
37 619882407
411 686801555
375 707664738
1011 397179763
788 970981046
234 562800989
459 74681058
431 318142136
805 14497941
106 225119020
290 952016915
936 18742783
967 29898906
240 336515360
510 170561900
576 295146058
958 123035365
802 307228573
120 662008305
251 745153294
375 629190218
933 922489870
651 89894368
1113 100756163
1036 119183806
78 46638137
164 125958878
245 765198061
54 476780353
1173 927983877
1175 274537380
512 902048682
408 170637900
201 79831242
448 677923623
412 354613949
390 981383102
905 371206425
352 336460103
1098 950229531
1034 905673027
429 511009805
1013 910772987
180 456887287
438 247636551
249 311923987
710 671797755
410 107508299
281 440965211
208 887321399
694 773237744
463 137283561
99 835520296
218 849667314
38 938051866
563 754913026
312 159991251
919 140795251
952 777906307
270 811402038
135 172573170
225 17639789
568 830945700
866 983903519
505 620193777
276 292351330
603 609206166
1119 417994586
76 622537983
751 702461295
839 603688893
341 957089047
365 814148222
361 108497049
145 550713329
126 535279139
136 382991595
115 224756633
1032 252485168
152 79105654
369 299471948
883 433113382
325 641184196
181 366626105
225 89560602
796 112596419
832 938621936
611 158705500
929 34104497
144 491851531
355 498362401
1084 725169559
697 892731447
197 187385980
1122 928756628
863 56409088
344 517927691
74 145932225
1030 487801476
43 354066192
18 578959792
585 75953285
317 995963609
383 244192305
764 311066684
1050 582487991
1108 860889677
804 302667723
10 703414589
397 130697818
1025 151133729
967 444985552
1189 223945261
663 147467216
67 59026498
1130 875978182
238 687257432
1082 485680041
1033 577064440
777 484268886
1158 663017804
421 112957672
582 101147152
446 846055510
154 868250052
721 10067160
97 287580811
260 946829140
177 6257680
1192 404109647
446 443900361
1197 835632037
454 838786312
757 191532162
481 101544753
613 674585582
406 21003890
463 382233676
892 801711460
548 268425267
1114 524049906
550 62568698
95 761546725
1094 764100447
275 957121396
698 553577883
1181 116268098
445 764807253
1065 240753431
928 391937991
511 965049031
547 427812984
420 54567068
566 554750191
476 322630821
848 590337977
888 537970255
97 886280486
309 215032736
192 673359905
595 396799863
348 473909617
3 524057913
691 806414047
375 999259708
866 731015052
1088 238018396
1141 870832854
936 658329880
743 555533118
680 728011405
283 108997281
694 566472642
922 387236129
1200 644359056
771 375369770
713 796458904
508 12337901
82 800305816
235 775257516
272 323313549
31 246063429
848 918515188
989 718160967
1130 174251925
784 951588614
469 64934967
145 737259013
242 205405584
884 606512142
859 279213031
977 59209580
44 858896821
1142 739053964
497 269352107
332 350787717
35 398581378
653 865114056
1193 822591472
381 807830381
433 963687458
478 421970804
533 682578205
41 59097181
396 766119777
568 15427700
1042 123045689
556 137391414
165 158983182
889 903768619
97 141112859
994 77998738
881 678043376
258 862639945
200 95039252
359 203905097
261 831771950
257 321793300
622 969992986
175 72656769
420 849294651
1001 830950966
1040 828243064
117 220261947
987 418327361
66 294650119
726 804271092
886 280646748
552 696461072
1172 383073629
713 244145026
860 606558266
1086 867939208
132 352671187
786 725581418
779 20030635
11 496030085
765 86772889
915 791753462
686 516573834
117 341214284
143 292648380
294 276715937
17 70172108
633 137883511
217 979846392
792 568188349
942 26401283
707 942515293
311 647047422
85 421626790
504 782112883
670 170593542
123 652404290
420 11557479
489 401160597
908 330968720
142 313561416
866 206132972
430 112044586
755 838589212
294 85279344
1119 877307049
319 611481540
733 293648702
70 444315457
76 429430730
767 320378578
719 206892773
121 327881014
737 427734237
328 876205100
823 769145289
205 28010503
1199 356753919
486 120662048
727 961912662
945 258387833
412 313697671
848 813831421
931 163999768
768 320897706
1033 58352176
842 54007584