0 0
1 0
2 1
3 0
4 2
5 1
6 5
7 2
8 9
9 5
10 17
11 9
12 30
13 16
14 49
15 26
16 78
17 43
18 122
19 67
20 184
21 101
22 272
23 151
24 397
25 222
26 567
27 320
28 802
29 454
30 1121
31 637
32 1545
33 884
34 2112
35 1214
36 2863
37 1651
38 3842
39 2227
40 5123
41 2979
42 6782
43 3957
44 8913
45 5218
46 11648
47 6840
48 15136
49 8914
50 19555
51 11552
52 25143
53 14890
54 32175
55 19101
56 40979
57 24390
58 51977
59 31006
60 65664
61 39255
62 82620
63 49504
64 103587
65 62191
66 129425
67 77855
68 161150
69 97131
70 200030
71 120782
72 247532
73 149729
74 305398
75 185060
76 375755
77 228066
78 461075
79 280301
80 564276
81 343589
82 688872
83 420088
84 838961
85 512368
86 1019348
87 623443
88 1235773
89 756858
90 1494912
91 916808
92 1804564
93 1108200
94 2173982
95 1336776
96 2613895
97 1609296
98 3136808
99 1933633
100 3757437
101 2318973
102 4492819
103 2776070
104 5362752
105 3317411
106 6390391
107 3957515
108 7602486
109 4713298
110 9030018
111 5604344
112 10709036
113 6653343
114 12681104
115 7886626
116 14994201
117 9334590
118 17703917
119 11032336
120 20874188
121 13020452
122 24578597
123 15345656
124 28902090
125 18061742
126 33942123
127 21230692
128 39810549
129 24923674
130 46636048
131 29222392
132 54565885
133 34220701
134 63768690
135 40026085
136 74437803
137 46761620
138 86794009
139 54568274
140 101089498
141 63607103
142 117612555
143 74062056
144 136691716
145 86143263
146 158701329
147 100090238
148 184068204
149 116175910
150 213277700
151 134711254
152 246881616
153 156049965
154 285507571
155 180594174
156 329867780
157 208800995
158 380770275
159 241189252
160 439131968
161 278347553
162 505991330
163 320943520
164 582524193
165 369733382
166 670061921
167 425573344
168 770109566
169 489432540
170 884367966
171 562406609
172 1014759015
173 645733666
174 1163451453
175 740812350
176 1332891615
177 849220985
178 1525838489
179 972739859
180 1745400023
181 1113376328
182 1995075800
183 1273391660
184 2278805569
185 1455331994
186 2601019930
187 1662063130
188 2966699431
189 1896807950
190 3381441398
191 2163189242
192 3851530388
193 2465277744
194 4384019751
195 2807644023
196 4986823245
197 3195417525
198 5668812600
199 3634352648
200 6439929450
201 4130900340
202 7311310690
203 4692289210
204 8295422924
205 5326616056
206 9406215422
207 6042944264
208 10659291216
209 6851414805
210 12072091330
211 7763369835
212 13664103265
213 8791487372
214 15457093744
215 9949932622
216 17475360008
217 11254526175
218 19746013136
219 12722927635
220 22299293435
221 14374841171
222 25168912060
223 16232243689
224 28392434750
225 18319634190
226 32011707769
227 20664312120
228 36073320724
229 23296685886
230 40629124347
231 26250610241
232 45736804297
233 29563762020
234 51460505836
235 33278055920
236 57871530238
237 37440099498
238 65049105615
239 42101698740
240 73081226931
241 47320416684
242 82065590090
243 53160185044
244 92110624360
245 59691982337
246 103336618239
247 66994582271
248 115876968725
249 75155373292
250 129879560004
251 84271265468
252 145508267960
253 94449690247
254 162944626200
255 105809695207
256 182389661945
257 118483153449
258 204065900612
259 132616095430
260 228219581261
261 148370166984
262 255123094892
263 165924237740
264 285077647738
265 185476170342
266 318416199103
267 207244756960
268 355506691549
269 231471852536
270 396755579114
271 258424718815
272 442611713199
273 288398589365
274 493570610960
275 321719491412
276 550179116510
277 358747343516
278 613040528060
279 399879344104
280 682820223652
281 445553694582
282 760251803659
283 496253682787
284 846143838860
285 552512147824
286 941387266909
287 614916380285
288 1046963466923
289 684113491995
290 1163953118953
291 760816284390
292 1293545906086
293 845809682502
294 1437051102923
295 939957779272
296 1595909179613
297 1044211530222
298 1771704499212
299 1159617181451
300 1966179169424
301 1287325489242
302 2181248207248
303 1428601785911
304 2419016118799
305 1584836994355
306 2681794978348
307 1757559667669
308 2972124202263
309 1948449126870
310 3292792150431
311 2159349823715
312 3646859670677
313 2392287028402
314 4037685826969
315 2649483938518
316 4468955982944
317 2933380367549
318 4944712397744
319 3246653142148
320 5469387630140
321 3592238334692
322 6047840973494
323 3973355528953
324 6685398131170
325 4393534285085
326 7387894496775
327 4856642969826
328 8161722328127
329 5366920198629
330 9013882090512
331 5929009103274
332 9952038420554
333 6547994641263
334 10984581083000
335 7229444254672
336 12120691279765
337 7979452152609
338 13370413872822
339 8804687497391
340 14744735996765
341 9712446878471
342 16255672529647
343 10710711425432
344 17916359119726
345 11808208920644
346 19741153374650
347 13014481391993
348 21745744822388
349 14339958633935
350 23947274508881
351 15796038119642
352 26364465006648
353 17395171905560
354 29017761620179
355 19150961098450
356 31929485861727
357 21078258477604
358 35124002184856
359 23193280024229
360 38627898982240
361 25513726081529
362 42470185184413
363 28058912902632
364 46682503712872
365 30849915525945
366 51299363072356
367 33909722895320
368 56358388748739
369 37263406188686
370 61900595997318
371 40938301528896
372 67970685660090
373 44964208238245
374 74617365086434
375 49373603858899
376 81893696158043
377 54201877406342
378 89857472502552
379 59487582322330
380 98571628475543
381 65272710674132
382 108104682435893
383 71602990433513
384 118531216955286
385 78528207682662
386 129932399170528
387 86102555701655
388 142396544459862
389 94385013226098
390 156019726778544
391 103439754198117
392 170906439646448
393 113336591475870
394 187170311786085
395 124151457355432
396 204934881613397
397 135966923823638
398 224334435550044
399 148872765643250
400 245514915171140
401 162966569827148
402 268634898475348
403 178354395162588
404 293866661455088
405 195151485678915
406 321397326243439
407 213483042489569
408 351430102478755
409 233485058592087
410 384185629559022
411 255305221505587
412 419903427636126
413 279103889261500
414 458843465672084
415 305055145476697
416 501287856078625
417 333347939615630
418 547542685747155
419 364187319300414
420 597939993873408
421 397795761819730
422 652839908391401
423 434414612467032
424 712632953245318
425 474305638228380
426 777742539485604
427 517752705734558
428 848627654841188
429 565063592995593
430 925785766989326
431 616571945492455
432 1009755956712332
433 672639387724992
434 1101122299091662
435 733657802069471
436 1200517511661840
437 800051788060106
438 1308626889677107
439 872281315893054
440 1426192550951986
441 950844588893460
442 1554018013774301
443 1036281131194886
444 1692973132934195
445 1129175117761512
446 1843999421642759
447 1230158965060868
448 2008115788485783
449 1339917202499504
450 2186424720484533
451 1459190645861543
452 2380118946581956
453 1588780895459120
454 2590488617653192
455 1729555183861830
456 2818929041539140
457 1882451599511121
458 3066949015473516
459 2048484714348252
460 3336179800554456
461 2228751646172511
462 3628384785904384
463 2424438588271390
464 3945469894776986
465 2636827841117890
466 4289494787774469
467 2867305384043094
468 4662684922063956
469 3117369027089081
470 5067444530982587
471 3388637186031664
472 5506370592108947
473 3682858327311058
474 5982267856492185
475 4001921132483954
476 6498165018301418
477 4347865435249709
478 7057332108819232
479 4722893988616029
480 7663299204391844
481 5129385123359153
482 8319876545825082
483 5569906363174135
484 9031176172561738
485 6047229067344641
486 9801635181982277
487 6564344176232828
488 10636040733629908
489 7124479140104355
490 11539556925448528
491 7731116118353877
492 12517753677754097
493 8388011541749325
494 13576637772013466
495 9099217136711472
496 14722686200564185
497 9869102518551685
498 15962881994029825
499 10702379467461580
500 17304752706809198
501 11604128008891170
502 18756411752265037
503 12579824429500409
504 20326602792262457
505 13635371368344604
506 22024747402078914
507 14777130132561632
508 23860996245631556
509 16011955398356334
510 25846284011902352
511 17347232468512628
512 27992388383146329
513 18790917269419157
514 30311993322638029
515 20351579284507722
516 32818756989190843
517 22038447633833243
518 35527384609413331
519 23861460523880555
520 38453706659775275
521 25831318308482324
522 41614762734356844
523 27959540417476708
524 45028891502718660
525 30258526427239667
526 48715827188237154
527 32741621567518600
528 52696803026294248
529 35423186978271212
530 56994662196089623
531 38318675051541471
532 61633976751594588
533 41444710217914258
534 66641175112546619
535 44819175560647541
536 72044678717775178
537 48461305666546122
538 77875048481996950
539 52391786152229640
540 84165141740248060
541 56632860333197303
542 90950280413978316
543 61208443534668751
544 98268431180260656
545 66144245578886497
546 106160398477849605
547 71467902018610954
548 114670031243885157
549 77209114724889580
550 123844444332827110
551 83399802480264414
552 133734255632685851
553 90074262271243862
554 144393839965935962
555 97269342020388648
556 155881600932817592
557 105024625550338107
558 168260261931741038
559 113382630623956773
560 181597177678546949
561 122389020961172409
562 195964667631854636
563 132092833195759306
564 211440372825025591
565 142546719798263092
566 228107637710008908
567 153807209059559511
568 246055918722114256
569 165934983305091601
570 265381221387645081
571 178995176586148147
572 286186567922364718
573 193057693177186330
574 308582497394569226
575 208197548299215856
576 332687600663024391
577 224495232581706662
578 358629092451648620
579 242037101875376100
580 386543423075116953
581 260915794137806345
582 416576932494454326
583 281230675225704077
584 448886549563983162
585 303088315548247242
586 483640539515166138
587 326602999667880700
588 521019302921925702
589 351897271070123050
590 561216229611082181
591 379102514469506259
592 604438611204077708
593 408359578177475412
594 650908616216167155
595 439819439221310713
596 700864331902395309
597 473643914078638368
598 754560877308267515
599 510006418082910924
600 812271592272169701
601 549092776752139516
602 874289307442565092
603 591102092504597412
604 940927700696820332
605 636247670454493324
606 1012522745696581757
607 684758007217921586
608 1089434258693858083
609 736877846913896874
610 1172047550091984190
611 792869308820633498
612 1260775187684330026
613 853013091432978956
614 1356058878948513936
615 917609757972992099
616 1458371480243202151
617 986981108736165338
618 1568219141257825240
619 1061471645999547986
620 1686143593610869160
621 1141450137585866196
622 1812724593056688396
623 1227311285574216660
624 1948582525365157020
625 1319477507061088861
626 2094381186591872281
627 1418400834317205261
628 2250830749134526119
629 1524564942160989771
630 2418690925696264537
631 1638487310865689004
632 2598774344059364284
633 1760721533447248747
634 2791950146386200817
635 1891859776749530418
636 2999147827634048516
637 2032535406338926148
638 3221361328606873736
639 2183425785856028202
640 3459653400143004619
641 2345255262153902896
642 3715160255979514226
643 2518798348266546560
644 3989096532954534708
645 2704883117012650030
646 4282760578377904094
647 2904394818855819457
648 4597540085648155649
649 3118279738497900042
650 4934918100533246623
651 3347549305593863687
652 5296479421932388065
653 3593284475952662053
654 5683917422429058762
655 3856640400612652777
656 6099041315545595334
657 4138851401271186892
658 6543783898284774956
659 4441236271714407996
660 7020209799328499768
661 4765203926118599756
662 7530524265174692631
663 5112259416398863194
664 8077082518496086899
665 5484010342174213634
666 8662399725136910172
667 5882173678382990839
668 9289161608444149136
669 6308583047141050327
670 9960235752022466180
671 6765196462098475421
672 10678683634547802323
673 7254104575300444627
674 11447773442994937553
675 7777539458418818572
676 12270993713490332064
677 8337883952205375077
678 13152067852039391288
679 8937681620106596678
680 14094969590619843604
681 9579647344200384922
682 15103939437540174921
683 10266678603981088439
684 16183502184584286451
685 11001867481011254244
686 17338485537326444420
687 11788513435106266852
688 18574039939062651017
689 12630136900537367362
690 19895659663120720402
691 13530493753709382288
692 21309205252910672704
693 14493590706924697907
694 22820927393916411318
695 15523701686202475251
696 24437492306969378800
697 16625385254661420046
698 26166008757617865222
699 17803503146731881980
700 28014056782167120999
701 19063239982458992899
702 29989718237082057796
703 20410124235372371144
704 32101609284953026382
705 21850050531869725738
706 34358914937080025427
707 23389303364814728806
708 36771425780005335354
709 25034582309063104976
710 39349577021060460678
711 26793028831949524249
712 42104489996143851372
713 28672254797418136084
714 45048016291592279299
715 30680372768440891059
716 48192784641197948512
717 32826028218689745240
718 51552250769108514300
719 35118433771141703103
720 55140750359617648548
721 37567405588379408271
722 58973555345763168084
723 40183402046859924504
724 63066933720150962435
725 42977564835394987692
726 67438213083615167804
727 45961762626498378939
728 72105848160269234271
729 49148637478171785836
730 77089492521151954627
731 52551654133159157207
732 82410074773137478255
733 56185152392683640184
734 88089879485128100389
735 60064402752259476212
736 94152633139737691939
737 64205665498389270230
738 100623595415824843155
739 68626253476799302790
740 107529656125426879211
741 73344598755409050995
742 114899438147835761716
743 78380323418528227638
744 122763406723881200859
745 83754314742812514669
746 131153985495035024675
747 89488805020374319791
748 140105679694684290008
749 95607456310197526581
750 149655206922991058934
751 102135450415636014085
752 159841635962267415062
753 109099584403382069198
754 170706534116709856102
755 116528371997941927102
756 182294123588827969296
757 124452151205346974454
758 194651447435086736812
759 132903198540670214244
760 207828545675130414256
761 141915850255988271016
762 221878642162659815705
763 151526630988730855473
764 236858342861729746080
765 161774390275015713732
766 252827846209897676515
767 172700447398669978572
768 269851166289503370134
769 184348745074197093730
770 287996369570547572325
771 196766012491101715501
772 307335826033155091979
773 210001938277839946317
774 327946475524694994508
775 224109353976236413844
776 349910110256467097458
777 239144428651661312200
778 373313674397451691166
779 255166875300712886965
780 398249581778229984680
781 272240169756632578300
782 424816052777022578006
783 290431782833370689050
784 453117471521880371633
785 309813426492262550492
786 483264764608703348414
787 330461314860711031524
788 515375802604195655464
789 352456440980304737429
790 549575825676127988288
791 375884870212597416851
792 585997894770717552154
793 400838051284391798495
794 624783369838826154064
795 427413146011042070781
796 666082416699080272949
797 455713378796204889980
798 710054544217326648148
799 485848407069707746503
800 756869173578369283706
801 517934713892029810744
802 806706241527780847546
803 552096024024525962726
804 859756839569189282448
805 588463744839071813290
806 916223891216174427040
807 627177433519567655219
808 976322869517897793356
809 668385292090969656813
810 1040282557204337753526
811 712244691899347977996
812 1108345851930935046221
813 758922729259248417264
814 1180770619243740985493
815 808596814082654844357
816 1257830596035379273203
817 861455293407279013650
818 1339816347419771165607
819 917698111851136367614
820 1427036280119855591281
821 977537511135747120570
822 1519817715638117755906
823 1041198770942036829505
824 1618508026665187691090
825 1108920993491550767749
826 1723475840377368675498
827 1180957934381343508658
828 1835112312480454556576
829 1257578882344112664273
830 1953832476075249294736
831 1339069590756330707499
832 2080076669650170365894
833 1425733263876757743630
834 2214312048749056577430
835 1517891600966101107925
836 2357034186118568399189
837 1615885901616318232465
838 2508768765409811904899
839 1720078235805678786854
840 2670073373794014982707
841 1830852682393587962362
842 2841539399153115273203
843 1948616639978006676986
844 3023794037823533674566
845 2073802214258714858394
846 3217502419206326269402
847 2206867686282107561333
848 3423369853910349606049
849 2348299066188473962644
850 3642144212467711890248
851 2498611737341515968660
852 3874618442053901220786
853 2658352195992766428568
854 4121633229059761364717
855 2828099891921467741430
856 4384079815799742941404
857 3008469175794217564938
858 4662902980102068093817
859 3200111359308939026015
860 4959104187012976618814
861 3403716894525525387213
862 5273744922360059362324
863 3620017679141827874634
864 5607950218460523173512
865 3849789494849288363534
866 5962912382830655311259
867 4093854586298660615830
868 6339894941353952880448
869 4353084388624057470487
870 6740236807999298748966
871 4628402411913945666472
872 7165356693849036850639
873 4920787291482061803648
874 7616757768901250589874
875 5231276013280868679003
876 8096032590853213326958
877 5560967324316226621044
878 8604868315855989985284
879 5911025338466006773230
880 9145052207055222439830
881 6282683348678962321601
882 9718477457602800310822
883 6677247857134621866248
884 10327149345740872225550
885 7096102835582106901658
886 10973191740525511844291
887 7540714228747390292218
888 11658853977775278401146
889 8012634714406168211334
890 12386518126902764611660
891 8513508734465326158344
892 13158706670417404693679
893 9045077812182015128866
894 13978090619078730405976
895 9609186171477461553271
896 14847498086934230055756
897 10207786675175251944736
898 15769923351797824521547
899 10842947099913367496568
900 16748536428117651098058
901 11516856766447868242528
902 17786693180649185057826
903 12231833545086655068336
904 18887946008895083934828
905 12990331257066963139680
906 20056055133901034400363
907 13794947493822718142572
908 21295000520711772044868
909 14648431877280866192019
910 22608994471597282238628
911 15553694785582508173019
912 24002494927061190952174
913 16513816569948131068690
914 25480219513646680176648
915 17532057289800184127385
916 27047160379664562703831
917 18611866994724452769352
918 28708599862189439391382
919 19756896583397657101392
920 30470127031009117960874
921 20971009271236777642759
922 32337655157675157603952
923 22258292700240143455637
924 34317440160395452918496
925 23623071726295428135938
926 36416100078240109640253
927 25069921921130391920888
928 38640635631005899097132
929 26603683828083531162354
930 40998451924110305878412
931 28229478012978569682532
932 43497381361071625004696
933 29952720953604731183651
934 46145707829484222295783
935 31779141813639816674651
936 48952192229927170291269
937 33714800149310908005538
938 51926099420959299227164
939 35766104599674705293243
940 55077226657263031140154
941 37939832614122858028937
942 58415933602113839115422
943 40243151273583741070484
944 61953173999682542592252
945 42683639264908669504632
946 65700529097234162542922
947 45269310071105388518760
948 69670242912081997572876
949 48008636443422481422395
950 73875259443201382531551
951 50910576224804018024116
952 78329261932716216406532
953 53984599597933403804608
954 83046714288056963275435
955 57240717834977917588194
956 88042904781465830452644
957 60689513630241129166557
958 93333992149707156547993
959 64342173101239786732874
960 98937054223345042260360
961 68210519548255251675668
962 104870139221792575832572
963 72307049067179015359445
964 111152319857533883513336
965 76644968115489429963384
966 117803750400490527301973
967 81238233136474613708680
968 124845726861466729111295
969 86101592352368266912482
970 132300750461982418564293
971 91250629842904939306286
972 140192594566610931548460
973 96701812031943172835492
974 148546375263201583467270
975 102472536711264743514409
976 157388625786108274430004
977 108581184737452225000500
978 166747374987788842518592
979 115047174544891614471073
980 176652230074911785622274
981 121891019625460077889932
982 187134463836432745888640
983 129134389133359814075594
984 198227106603011728755120
985 136800171781866544196552
986 209965043189663128081017
987 144912543207496303305804
988 222385115086693880018524
989 153497036986278803375073
990 235526228177823837038404
991 162580619496481619063286
992 249429466278931067517155
993 172191768832281163888783
994 264138210806157615879074
995 182360557983549017478040
996 279698266898186775183668
997 193118742508141095734316
998 296157996334400768978692
999 204499852934870512451688
1000 313568457608387754209210