1 2
2 1499
3 1783
4 9719
5 9311
6 67883
7 134947
8 203317
9 189433
10 560171
11 438533
12 943849
13 640973
14 578827
15 2172383
16 28687
17 1505657
18 7595033
19 2822971
20 1242379
21 22899523
22 9232219
23 5730031
24 12336083
25 3487607
26 35451433
27 12174803
28 10234079
29 84459019
30 68736683
31 44671169
32 85507057
33 103260119
34 22478971
35 79035049
36 136537
37 107039071
38 243754463
39 249787423
40 159438341
41 2279933
42 233272727
43 219624319
44 645202963
45 376111891
46 111369211
47 509858803
48 1100204377
49 333691019
50 748516033
51 840925433
52 1354433783
53 716203361
54 1143729137
55 363109801
56 4406477
57 1083762059
58 1333434313
59 2116924471
60 2277914833
61 1954449919
62 602358283
63 1983598619
64 467296399
65 1357852303
66 1939743083
67 4659763627
68 1600751611
69 5479228423
70 1437069787
71 4654886801
72 707532983
73 425323117
74 2306166307
75 3215265433
76 2903316487
77 7109149651
78 5330927629
79 7452416029
80 7528822993
81 942359837
82 3407132107
83 7634616211
84 4425047233
85 2612138483
86 639269119
87 11567963053
88 10704247369
89 12170593817
90 8774533483
91 10368837569
92 10650124883
93 7232129309
94 6571059431
95 1350557119
96 8370124687
97 681181393
98 8485991483
99 9085010651
100 10066174109
101 12003366619
102 3187758403
103 19403246251
104 21809983007
105 2554798583
106 7439872897
107 6193392983
108 573956281
109 13845314719
110 12392586827
111 1201011463
112 1553106481
113 19273063321
114 12969602309
115 32988098797
116 1729399319
117 5177425717
118 1309489297
119 27161121313
120 23450131577
121 31659376501
122 6516355033
123 9099553763
124 19963574551
125 14175993107
126 28119173183
127 3784567051
128 6001445633
129 9717870619
130 33099134821
131 21602602369
132 40923044299
133 12436251649
134 29141770033
135 39011372683
136 14504093083
137 20319131423
138 29894025869
139 56952643919
140 6583172119
141 62528027351
142 10684749983
143 47897982019
144 192575899
145 24656903603
146 12718468949
147 25735157029
148 1092807451
149 68800816769
150 19989209183
151 79132253869
152 15272236531
153 63560994449
154 29319707863
155 83304201133
156 20421634901
157 24278892751
158 32040507377
159 51058846439
160 73411629623
161 91137919339
162 103801064869
163 10661093783
164 99559842013
165 69002370869
166 20264376383
167 134652213349
168 40658011649
169 109482800111
170 42965941969
171 100250305609
172 41341841911
173 165909126259
174 26505960139
175 97586002093
176 37967677519
177 96519248887
178 24739898149
179 12319839019
180 153924917869
181 74593309771
182 63767551591
183 27487123997
184 103440799447
185 143865821083
186 107763002833
187 46938503669
188 34460972983
189 143237052043
190 103933072297
191 53790348463
192 181473572719
193 17783543269
194 145487888531
195 142669643383
196 187201842283
197 149766379067
198 222047047883
199 145008641341
200 170810103469
201 257160984517
202 147648774719
203 123205136933
204 90380427233
205 47146466827
206 63530365903
207 199602830027
208 32779328419
209 15636716119
210 13221407033
211 107239775329
212 309484859443
213 187600349821
214 282943285769
215 272687446253
216 41155436677
217 170257245311
218 232697317819
219 299214393229
220 220092401713
221 80396377349
222 5799669157
223 339212660851
224 112745762993
225 195304497827
226 275032977697
227 320807522647
228 11090446183
229 236487014021
230 82166852351
231 368770911533
232 287244970633
233 289082847413
234 267931597667
235 10852485433
236 392754325571
237 147958333183
238 422448139187
239 92702182943
240 2774886839
241 12431401397
242 467838572689
243 413406123583
244 265695726097
245 167147509519
246 468790585453
247 187568365951
248 38391662233
249 264267122783
250 215492529709
251 256331866447
252 257956359569
253 214305710401
254 523600307519
255 25425187171
256 164231592769
257 534244135333
258 537596361019
259 288452946583
260 504896716801
261 86953431283
262 218033914159
263 360310494241
264 321050178583
265 342830651203
266 634763759221
267 141552698851
268 566292751919
269 675741189637
270 435690607529
271 633811991819
272 192481700483
273 166014662117
274 514262761651
275 353476089163
276 216232482197
277 9513290681
278 227899536769
279 203823438121
280 603808727779
281 111585881233
282 149680709929
283 551064700019
284 352418400127
285 392236490983
286 9367605019
287 882966101833
288 915032550769
289 609628200211
290 795134946371
291 482475679633
292 450203727469
293 422178756239
294 1024423591237
295 1044936858089
296 886503998719
297 673636789009
298 695717069783
299 983788022953
300 869332134691
301 793255654459
302 715364167933
303 212231030419
304 552693246797
305 200454130027
306 549266436559
307 715031162569
308 523172682083
309 496485457483
310 891723870461
311 683658533023
312 917429812933
313 1269384800833
314 614650282289
315 308134239601
316 444292013521
317 829551508283
318 757476459871
319 812271841669
320 27499733531
321 917759166913
322 903954722743
323 631513259953
324 1433099543059
325 1592709647383
326 1504182811933
327 1480983464501
328 907574590459
329 1496307045917
330 554299057063
331 1192099377019
332 1550480728591
333 494377862047
334 288160399573
335 1477304513239
336 742305638719
337 942501047563
338 1611279570619
339 1807455740033
340 549411796147
341 149517369299
342 1094733693721
343 1712171788003
344 8507080783
345 1655236440019
346 650893390957
347 815008699819
348 981485715251
349 435935027783
350 418100072167
351 181090809919
352 372952366363
353 1724417422543
354 485854385167
355 1054992581833
356 1017419236201
357 1354652392033
358 530853665977
359 236558957699
360 1691370110233
361 2240562133853
362 354511446769
363 1569111753889
364 543450503719
365 347326762919
366 2374016418283
367 433778393651
368 1857015724429
369 2414985752251
370 2048242767419
371 138731658067
372 538341184547
373 1913322236311
374 1200303076663
375 1447046240533
376 1017825224257
377 2625787846009
378 790703891177
379 1254323992513
380 1900189557269
381 794508749029
382 15862391191
383 154182511477
384 1465023870593
385 1280774339057
386 1122431219999
387 1256738128769
388 1854329771233
389 2923742695969
390 103259978567
391 1810280194483
392 1592332576283
393 2046997419427
394 1466743448719
395 1571396898943
396 2408599907887
397 409225017241
398 1478770621183
399 1820643176663
400 2814749383681
401 438521646611
402 986083918279
403 2378228693021
404 910972664333
405 2072202748669
406 1899800468173
407 2464400273033
408 801959578489
409 3116135243719
410 3462035326333
411 1058472030839
412 2374098904217
413 2240563559911
414 2533215307277
415 3746222371211
416 3199636934183
417 3481139386883
418 2979697818059
419 1719363064043
420 1108758250123
421 470895190417
422 2926119666341
423 618915921461
424 1242262380277
425 3046550599369
426 1850597628301
427 2749734028193
428 3888004042333
429 820996201633
430 2245121861669
431 1250676994159
432 1552633965977
433 736201313101
434 3980405785661
435 1538378265733
436 2481244684769
437 1990706674609
438 3677722436083
439 1721119702699
440 534300675929
441 980819536933
442 2256665037983
443 2161913996551
444 1391992133759
445 3728468545741
446 413066675419
447 334630468693
448 1032579020233
449 4065425687051
450 2837108879497
451 2146443614389
452 1622598711269
453 1289734733593
454 2717356362179
455 3760479130519
456 1548166235519
457 5210782719931
458 2792333120257
459 3612305152873
460 431788186073
461 4268301329449
462 338768443147
463 508647701239
464 3877119597511
465 1946992419607
466 954558762671
467 799301045017
468 2211481167869
469 950955522269
470 175089198457
471 1394889608669
472 921925137569
473 1060715969497
474 4226189072881
475 1466663761889
476 5590513227907
477 5315987431133
478 3911223946811
479 974971538083
480 1898168945683
481 135705467017
482 5389361420581
483 3350715482287
484 4452598959833
485 257417417249
486 5585673289841
487 511777428769
488 2503212780583
489 1208389681547
490 5102642203669
491 5173867763653
492 5988261740491
493 3870115482539
494 6615889039127
495 352087250863
496 4431322159949
497 614344760671
498 2415440520217
499 5545507775707
500 3693811069801
501 4207563058607
502 5283690028907
503 7373495990767
504 762815199709
505 6208874784349
506 3068170594733
507 513836860319
508 5098199700241
509 5220216357607
510 1147104329897
511 7422748089907
512 5863024265869
513 5349810105383
514 180951436697
515 2894509664857
516 2016379835693
517 2274793736597
518 6059456063723
519 4412049215999
520 7943909145049
521 8395207707853
522 1120776917719
523 5983028810701
524 7262074508959
525 5386825851769
526 697521687607
527 5831655837247
528 5006548666627
529 4931240511317
530 5641028712119
531 7308147053099
532 6285728021137
533 4938927473251
534 8003279618753
535 7830839093719
536 308805639169
537 5714681684233
538 9728918790607
539 6453684371833
540 7181519096683
541 2496500189669
542 5604785707819
543 5944287328883
544 822869782687
545 8023154350843
546 733210485131
547 2506992763883
548 1877000218573
549 1820006910613
550 2302273616813
551 1660850659747
552 1399750816033
553 3931152288409
554 4551771844369
555 3256057533257
556 8682868820513
557 1595109266533
558 4798588829927
559 1460418017837
560 5524682022443
561 408957091463
562 10637399701603
563 2061046089967
564 11483225315477
565 10728193957219
566 3931557354031
567 7436673596047
568 3148410670579
569 11354203903363
570 11916440121403
571 2801537626519
572 5381107948969
573 10643549736277
574 6730050797443
575 11849146640839
576 11101130564297
577 12519484232557
578 4860965217169
579 5851727440219
580 9136505656919
581 6399343871561
582 9326182468513
583 6582219260957
584 6059810054447
585 7941468031633
586 1055056447369
587 12222702066119
588 5729337728531
589 2349680377939
590 9555616983511
591 9322339557151
592 3744380598733
593 10024029124699
594 8414486134519
595 13995751015657
596 13942189218637
597 9067024211569
598 1020471025781
599 7087417614523
600 8104289274919
601 10505173640033
602 9597166407739
603 7439352806719
604 11174796621403
605 4739612495743
606 7274150768719
607 5208701969183
608 12335913828841
609 3214366453621
610 9207397207781
611 15702001969609
612 1299027743119
613 1659145406833
614 1339210681621
615 9127228892581
616 7918500686717
617 2315208087551
618 13565056233241
619 10903401353191
620 5723133070231
621 3538479155287
622 4372768109063
623 150113932939
624 14570935634413
625 9520828859053
626 3493417585069
627 474963920749
628 16228349878283
629 1122994590589
630 11324041623163
631 17193927658741
632 16825086572941
633 910953470503
634 16392939193483
635 519363605809
636 14584477186133
637 14933142853201
638 15734388142981
639 3952802654357
640 14780881116949
641 11979930354149
642 7465860637771
643 18585184977883
644 6414197625001
645 17449377675967
646 3399263744689
647 11489061877129
648 2228544323933
649 5148539603677
650 17580864323377
651 10557874944791
652 14860554573383
653 16778113277521
654 9312379343173
655 6268477519729
656 8614461792997
657 8184081972533
658 11300175646219
659 7395514880939
660 11283125342233
661 5649772214413
662 13067501435999
663 8245382666539
664 19522548633547
665 2462004533647
666 12153817307363
667 425021615519
668 161006295701
669 5919784417711
670 7853325333193
671 5869293905311
672 457181272931
673 18948755074393
674 781943969579
675 18103119753167
676 2751396818383
677 15091402546711
678 23013334028059
679 9034115098069
680 2573972842561
681 11024876866681
682 11062064402569
683 23901225972823
684 8747011969669
685 15003242443513
686 7715023118233
687 4297220631709
688 5667934044403
689 6747446350039
690 22336244385431
691 17102293514641
692 18889966819483
693 12496069667747
694 770159522213
695 15121287335839
696 12943821579079
697 23839437831227
698 11966655980497
699 8760796312069
700 20257587454249
701 2514513562277
702 25575281576609
703 20252612232383
704 14762826590761
705 20906986627459
706 16997714848747
707 15842954770583
708 5872677223519
709 23242201675723
710 17413604562223
711 21095139265169
712 643911601127
713 1440904357301
714 24404323560233
715 14665540904983
716 11323807547071
717 18950454875917
718 7293534939583
719 3736885376599
720 5911088106619
721 2051010308899
722 2489868793241
723 18219871721899
724 9213101965831
725 10605102237727
726 27751155619987
727 22398637131799
728 11793637314379
729 29117959835303
730 22899898056083
731 27520559012729
732 14679644947783
733 18909743524327
734 19945846666549
735 26681786817443
736 13169676676183
737 28014686562601
738 23375139136273
739 21367638006233
740 18182473464079
741 2465785496983
742 11243565832861
743 17336741317183
744 7275163040623
745 28069563899633
746 7455619659113
747 11572077900083
748 21073701878533
749 23296952839159
750 4661796228403
751 30832813741517
752 18130221367619
753 33704245613471
754 11596190879107
755 431009775491
756 23974355004569
757 32497834334599
758 15311801327843
759 21102128667649
760 8730896696527
761 1291059057689
762 1635548566297
763 24568298507491
764 17313060625097
765 12364003377533
766 36151558877377
767 14515346950933
768 12523743259583
769 17881899133933
770 30620242353607
771 15487132822243
772 18560048335061
773 22321169184331
774 35730787985569
775 23769481191319
776 14020483940167
777 22197080435683
778 28272181321411
779 36057588726079
780 32283654381541
781 24578860719433
782 35438037648001
783 31446428115433
784 24783518854333
785 37505399323897
786 22360272773437
787 4677438717709
788 2425222793393
789 16693444884617
790 19884225040723
791 37501421583121
792 18181738721453
793 32147681144077
794 38245702962589
795 28441901379259
796 32987225840479
797 14813520151987
798 35147464672259
799 16377546777953
800 11644236594973
801 33727316721017
802 26884209950659
803 8297865155863
804 10338871104811
805 20721703917833
806 27551937685339
807 19193920379629
808 655606280377
809 29490485293637
810 16869985269751
811 24407958104807
812 40999968841177
813 17790896944783
814 24760155281671
815 26703355185643
816 31244055990031
817 1143696884111
818 39383957524861
819 40400529415819
820 18839546004457
821 12243630389033
822 39248157531511
823 15481378446949
824 42479685028549
825 30059921405387
826 17393189104337
827 40387824822871
828 4553538993103
829 21378398906281
830 3977242285087
831 20949671987533
832 31925635717231
833 42821076050281
834 32464280775233
835 15766336531639
836 27935277062989
837 6954148072141
838 6215480214841
839 47881446420683
840 1703029983533
841 29960983403623
842 20020522628147
843 17597072604763
844 45330863776903
845 3717825270157
846 41941776626011
847 14709892588687
848 44577180866467
849 30315932936137
850 2553780175543
851 25647126342373
852 28116546378727
853 12333680866459
854 31133192030587
855 22904588850769
856 40876169982499
857 38443779166519
858 24066539626933
859 36131368359439
860 40226065402319
861 9534192409639
862 53275708021093
863 3542831106517
864 5643326235709
865 36356587709219
866 41215778421569
867 45890031378341
868 1381172327441
869 51422741803183
870 275738006197
871 33490205559583
872 32364794665757
873 37902828451219
874 1755152366887
875 11128072557853
876 21969697283291
877 54643287835153
878 4098771806951
879 10292395051711
880 10907894295163
881 44108016323069
882 41078841478919
883 24602183421619
884 11054795151683
885 27857351040983
886 24139439862119
887 48755144271553
888 20772760173167
889 27872292553579
890 4481992771819
891 23593038980419
892 11752845643237
893 40377057690349
894 34527643270853
895 27102715179247
896 39649497818993
897 21516704138549
898 62729804291743
899 24113913379489
900 62607298592437
901 16574498896069
902 47306505842083
903 62887127241229
904 23376288447313
905 3935468627747
906 9685147992497
907 40091505338237
908 44606317464883
909 31786329592099
910 47661560825869
911 21740981974787
912 23326623266117
913 46909897994503
914 38528588082169
915 4730026445693
916 57574515483883
917 2212550981983
918 34672977741979
919 51494693797271
920 68386804934039
921 25026874817149
922 44169072931117
923 46334864628667
924 66666157946029
925 48144902742121
926 10266373728379
927 14166442426141
928 17480837616481
929 39959874052933
930 44854218890017
931 56101761836431
932 7076767342699
933 16937771159579
934 4753726694179
935 70380946254413
936 7761495934369
937 4607751393433
938 11226064024621
939 60256789629373
940 22258421279287
941 62867691167707
942 55217922823319
943 68508829542019
944 4660086769831
945 16067987012393
946 13973697044599
947 8217347885497
948 67137262473383
949 20785051297333
950 37194554630719
951 32865675565213
952 42878684473381
953 20071866818429
954 14107217960273
955 20195168730427
956 1966259536693
957 7901346866993
958 29190040874483
959 9149007266339
960 38108416478659
961 4013899119883
962 80003738238751
963 14531817841603
964 21278534802823
965 69087829764817
966 78793722423253
967 69790189444777
968 28912676907043
969 20637716689069
970 71834464455119
971 46801717983883
972 9521229430309
973 83796659927003
974 9822434250683
975 44031129873733
976 43805381592563
977 30301028728507
978 20175768758683
979 33128864710483
980 69438375909533
981 28340365582967
982 22641817786163
983 11844694730989
984 63464227425869
985 82361362228931
986 34755214898659
987 50413364201911
988 13968749032703
989 88460910329833
990 53989812401419
991 38406352205293
992 89023008160747
993 29050027429627
994 9397582586167
995 80432225189707
996 56034537463199
997 84414746322331
998 79039598276467
999 87188308270919
1000 9475365440869