0    1
1    0
2    0
3    0
4    0
5    0
6    1
7    1
8    1
9    1
10   1
11   1
12   2
13   2
14   3
15   3
16   4
17   4
18   6
19   6
20   8
21   9
22   11
23   12
24   16
25   17
26   21
27   24
28   29
29   32
30   40
31   44
32   53
33   60
34   71
35   80
36   96
37   107
38   126
39   143
40   167
41   188
42   221
43   248
44   288
45   326
46   376
47   424
48   491
49   552
50   634
51   716
52   819
53   922
54   1056
55   1187
56   1353
57   1523
58   1730
59   1944
60   2209
61   2478
62   2806
63   3151
64   3559
65   3989
66   4504
67   5042
68   5679
69   6358
70   7148
71   7991
72   8978
73   10025
74   11241
75   12550
76   14051
77   15668
78   17528
79   19525
80   21810
81   24283
82   27089
83   30130
84   33586
85   37320
86   41547
87   46141
88   51310
89   56929
90   63257
91   70125
92   77834
93   86231
94   95617
95   105843
96   117275
97   129713
98   143586
99   158715
100  175536
101  193879
102  214271
103  236488
104  261141
105  288037
106  317810
107  350290
108  386233
109  425411
110  468704
111  515934
112  568028
113  624845
114  687487
115  755767
116  830955
117  912945
118  1003100
119  1101386
120  1209407
121  1327100
122  1456322
123  1597143
124  1751576
125  1919817
126  2104230
127  2305027
128  2524937
129  2764386
130  3026373
131  3311545
132  3623403
133  3962695
134  4333461
135  4736803
136  5177198
137  5656117
138  6178781
139  6746914
140  7366534
141  8039927
142  8773828
143  9571143
144  10439693
145  11382889
146  12409753
147  13524609
148  14737603
149  16054070
150  17485784
151  19039004
152  20727300
153  22558383
154  24547605
155  26704310
156  29046272
157  31584436
158  34339288
159  37324077
160  40562062
161  44069091
162  47872063
163  51989511
164  56452413
165  61282918
166  66516310
167  72178855
168  78311294
169  84944252
170  92124645
171  99888750
172  108290097
173  117371405
174  127194419
175  137808843
176  149285711
177  161683486
178  175083350
179  189553774
180  205188271
181  222066313
182  240295427
183  259968582
184  281208743
185  304124307
186  328856763
187  355531660
188  384311535
189  415342599
190  448810806
191  484886003
192  523781896
193  565694773
194  610869934
195  659535138
196  711971000
197  768441244
198  829268012
199  894755484
200  965273048
201  1041172525
202  1122876393
203  1210790922
204  1305400503
205  1407172831
206  1516662806
207  1634409906
208  1761048448
209  1897199858
210  2043590601
211  2200934766
212  2370063669
213  2551799006
214  2747090475
215  2956882533
216  3182261538
217  3424310910
218  3684272495
219  3963390300
220  4263081900
221  4584774283
222  4930087167
223  5300654854
224  5698326838
225  6124975964
226  6582711677
227  7073678405
228  7600283569
229  8164979311
230  8770511606
231  9419685492
232  10115629987
233  10861551440
234  11661016831
235  12517687199
236  13435626631
237  14419016086
238  15472482177
239  16600796487
240  17809227207
241  19103214851
242  20488755286
243  21972052081
244  23559924242
245  25259441185
246  27078358883
247  29024726940
248  31107363007
249  33335432319
250  35718953097
251  38268355189
252  40995020804
253  43910810448
254  47028650538
255  50362026919
256  53925611159
257  57734729465
258  61806032992
259  66156928508
260  70806306087
261  75773932109
262  81081225447
263  86750621510
264  92806403263
265  99274021102
266  106180994392
267  113556187708
268  121430773127
269  129837473071
270  138811591125
271  148390204112
272  158613279684
273  169522818625
274  181164048772
275  193584529190
276  206835429727
277  220970577797
278  236047845123
279  252128138241
280  269276881250
281  287562963769
282  307060331259
283  327846868692
284  350006123552
285  373626127289
286  398801239441
287  425630922612
288  454221721775
289  484685969002
290  517143927796
291  551722430166
292  588557174127
293  627791312017
294  669577918635
295  714078504441
296  761465689567
297  811921646129
298  865640966600
299  922829057343
300  983705222932
301  1048500982649
302  1117463412911
303  1190853392570
304  1268949192612
305  1352044677169
306  1440453167702
307  1534505569226
308  1634554559239
309  1740972648122
310  1854156684064
311  1974525879809
312  2102526667558
313  2238630660677
314  2383339919318
315  2537184859656
316  2700729924371
317  2874571479413
318  3059343932603
319  3255717585570
320  3464405274041
321  3686160193582
322  3921783060967
323  4172119962805
324  4438070092794
325  4720583592478
326  5020669954333
327  5339395880866
328  5677894360350
329  6037362606296
330  6419071876360
331  6824365464131
332  7254669371560
333  7711490390981
334  8196427649395
335  8711170858817
336  9257512822841
337  9837347834211
338  10452685280717
339  11105648242946
340  11798488233784
341  12533584096983
342  13313457997605
343  14140774610709
344  15018358533277
345  15949193838459
346  16936442966570
347  17983446774015
348  19093745055539
349  20271077095301
350  21519404035026
351  22842910031965
352  24246026562590
353  25733434356228
354  27310089833078
355  28981227847107
356  30752390529399
357  32629430987172
358  34618544687272
359  36726274331445
360  38959544039955
361  41325665476677
362  43832375178307
363  46487842132093
364  49300708446730
365  52280098673592
366  55435664161152
367  58777594249317
368  62316664749101
369  66064251291249
370  70032382212446
371  74233754441654
372  78681791242399
373  83390660848226
374  88375339630003
375  93651633866334
376  99236248732122
377  105146813713727
378  111401958012379
379  118021339927843
380  125025729412044
381  132437041951418
382  140278428823972
383  148574316157216
384  157350503672443
385  166634209400816
386  176454177870234
387  186840731202918
388  197825887509294
389  209443419269970
390  221728982974609
391  234720185487124
392  248456726173906
393  262980472238969
394  278335614391899
395  294568752355987
396  311729065449727
397  329868409266160
398  349041502795058
399  369306037612089
400  390722882975173
401  413356209130540
402  437273712204815
403  462546753030827
404  489250603966621
405  517464605056057
406  547272434723110
407  578762285410854
408  612027160565403
409  647165071708186
410  684279364508331
411  723478939738682
412  764878611072356
413  808599352785297
414  854768692479004
415  903520988227054
416  954997859903119
417  1009348499075794
418  1066730142497037
419  1127308418562593
420  1191257867205502
421  1258762326622192
422  1330015504415182
423  1405221409026038
424  1484594976905087
425  1568362553743007
426  1656762583294870
427  1750046143451570
428  1848477703098840
429  1952335718989395
430  2061913467043343
431  2177519706801595
432  2299479594622988
433  2428135422558554
434  2563847621856269
435  2706995584235014
436  2857978764263153
437  3017217592058952
438  3185154684416905
439  3362255858168800
440  3549011461145453
441  3745937496862217
442  3953577086747553
443  4172501718151631
444  4403312850907805
445  4646643301090858
446  4903159006530085
447  5173560560536660
448  5458585151589143
449  5759008262966673
450  6075645803887927
451  6409355991710643
452  6761041693791542
453  7131652511184852
454  7522187351453968
455  7933696735005091
456  8367285621683859
457  8824115962022142
458  9305409803008924
459  9812452109406328
460  10346594175534116
461  10909256744659161
462  11501933756940048
463  12126195796592374
464  12783694209429645
465  13476164911181236
466  14205432910179260
467  14973416513879593
468  15782132296456248
469  16633699743037479
470  17530346706218754
471  18474414532216979
472  19468364053310723
473  20514781244876818
474  21616383806154017
475  22776027400597705
476  23996712882852711
477  25281593180883027
478  26633981231224546
479  28057357567507513
480  29555379032961456
481  31131887144780836
482  32790917659962616
483  34536709792694142
484  36373716715357521
485  38306615714116347
486  40340319715789768
487  42479988473436219
488  44731041219003228
489  47099168980663275
490  49590348468982881
491  52210855638132591
492  54967280924725593
493  57866544174028512
494  60915911362550200
495  64123011023206059
496  67495852593313508
497  71042844486124983
498  74772814220587573
499  78695028298783763
500  82819214289274414
501  87155582686546774
502  91714851133943036
503  96508268458677221
504  101547641239305823
505  106845360226115880
506  112414429478145083
507  118268495400118377
508  124421878692925254
509  130889606260953009
510  137687446244397628
511  144831943072451598
512  152340455871812326
513  160231196968811308
514  168523273993561936
515  177236732163516255
516  186392600434282875
517  196012937925745953
518  206120884504271235
519  216740711748215107
520  227897878379362797
521  239619086202793545
522  251932340846197933
523  264867013146865346
524  278453905701166394
525  292725320217573079
526  307715130422207081
527  323458855946222698
528  339993742186016578
529  357358841343036337
530  375595099893767246
531  394745447459647413
532  414854892599177797
533  435970620249658173
534  458142096621826042
535  481421176020331119
536  505862215694454509
537  531522192921279053
538  558460830740950088
539  586740726269377219
540  616427488334364076
541  647589878069970311
542  680299959564457965
543  714633253887922513
544  750668903960795560
545  788489843273584933
546  828182976298086274
547  869839363269338748
548  913554417583996851
549  959428108143043809
550  1007565175309176444
551  1058075352447412337
552  1111073602159642601
553  1166680358805145588
554  1225021786888437989
555  1286230046507396533
556  1350443575936162265
557  1417807382127599038
558  1488473349721653404
559  1562600558917103057
560  1640355623339658406
561  1721913037811612205
562  1807455547728909455
563  1897174529488331676
564  1991270394265840623
565  2089953004105077563
566  2193442113252229653
567  2301967823184907472
568  2415771064937229697
569  2535104096646052615
570  2660231030613002562
571  2791428377261134605
572  2928985621019448548
573  3073205814937534355
574  3224406209838277493
575  3382918904221829292
576  3549091531535019420
577  3723287970404671791
578  3905889095308454370
579  4097293552633624792
580  4297918580499215894
581  4508200856630314848
582  4728597393599461590
583  4959586465034113586
584  5201668583106246599
585  5455367510177013355
586  5721231325963502311
587  5999833532359897882
588  6291774218375885738
589  6597681266553727371
590  6918211624493976010
591  7254052622041082843
592  7605923358984863628
593  7974576143003566566
594  8360798003984000327
595  8765412263586562869
596  9189280187552994138
597  9633302698724663900
598  10098422179701056932
599  10585624342190505715
600  11095940193478642550
601  11630448076116636255
602  12190275812846959294
603  12776602931874046442
604  13390663006172080984
605  14033746080927012558
606  14707201224556064546
607  15412439176355980069
608  16150935128086907225
609  16924231611450511439
610  17733941530730287089
611  18581751311445383245
612  19469424206338757391
613  20398803728407484930
614  21371817254480638671
615  22390479767860910821
616  23456897785835762090
617  24573273439370098688
618  25741908753196768935
619  26965210092376923287
620  28245692826111680945
621  29585986173588806652
622  30988838285348789024
623  32457121523656772231
624  33993837998200158831
625  35602125319267289290
626  37285262627744370056
627  39046676862707984817
628  40889949329132186342
629  42818822525106256288
630  44837207294423499100
631  46949190262526178966
632  49159041625223070410
633  51471223246710354646
634  53890397140065112287
635  56421434285293111510
636  59069423862045483649
637  61839682850614204009
638  64737766082520418441
639  67769476692797003232
640  70940877059714684705
641  74258300182562209100
642  77728361587897921103
643  81357971713380398118
644  85154348864565219684
645  89125032692246744008
646  93277898290985045958
647  97621170864902930142
648  102163441066928173901
649  106913680956075990680
650  111881260684841013613
651  117075965859794196303
652  122508015693689434816
653  128188081890734205888
654  134127308389906534166
655  140337331906558221698
656  146830303404193076657
657  153618910435259606942
658  160716400490265406469
659  168136605292742745490
660  175893966187206842225
661  184003560556384705677
662  192481129423203899857
663  201343106172614406842
664  210606646557579478627
665  220289659923237400398
666  230410841822922764825
667  240989707959079313184
668  252046629632722595522
669  263602870633606975487
670  275680625765329551525
671  288303060936838341546
672  301494355025769064006
673  315279743444550055013
674  329685563626634386699
675  344739302363424635359
676  360469645221918973094
677  376906527973535250272
678  394081190277565611434
679  412026231549845987978
680  430775669274414170726
681  450364999689104245412
682  470831261118067042889
683  492213099882891063505
684  514550839081452482026
685  537886550167233552230
686  562264127635463244048
687  587729366750228506446
688  614330044637226953483
689  642116004678209065683
690  671139244551228692463
691  701454007855120900304
692  733116879683092365620
693  766186886086700861972
694  800725597817209719899
695  836797238289106685539
696  874468796176261758936
697  913810142589670752148
698  954894153272351521499
699  997796835765168864146
700  1042597462005881009903
701  1089378706320880636874
702  1138226789300354784283
703  1189231627522901960825
704  1242486989650717246350
705  1298090658868861268542
706  1356144602222113277679
707  1416755146831541913760
708  1480033163578781531728
709  1546094258249922421716
710  1615058970763878207966
711  1687052982488135399559
712  1762207332306083464822
713  1840658641451315781866
714  1922549347815018969360
715  2008027949755853518028
716  2097249260163284250172
717  2190374670819395685248
718  2287572427858016024500
719  2389017918383750308914
720  2494893969100797412090
721  2605391157033717399182
722  2720708133244656066848
723  2841051959650887368105
724  2966638459905535512524
725  3097692584469530609274
726  3234448790899945478678
727  3377151439509564310124
728  3526055205489512744347
729  3681425507679373655809
730  3843538955147887650986
731  4012683811801452913004
732  4189160480259647185936
733  4373282005251147238713
734  4565374597850795857226
735  4765778180850953694034
736  4974846956675071783377
737  5192949998170509857301
738  5420471863781720689896
739  5657813237489055728393
740  5905391595114146580136
741  6163641897429994662571
742  6433017311783542941765
743  6713989962727013670922
744  7007051713480022886986
745  7312714978782479201046
746  7631513571082706681604
747  7964003580690492740350
748  8310764291970558741765
749  8672399136282571423050
750  9049536683883427019060
751  9442831675581467696795
752  9852966096508698154406
753  10280650292891843490895
754  10726624134349317890715
755  11191658222694675510161
756  11676555149945971961668
757  12182150806630418696651
758  12709315743268583509789
759  13258956586246074936532
760  13832017511154978941882
761  14429481774942384729910
762  15052373310160344129549
763  15701758382795541906584
764  16378747317200491621442
765  17084496289757867042322
766  17820209195043572758062
767  18587139586287221315448
768  19386592694156822772386
769  20219927525848043749387
770  21088559048785064350345
771  21993960461110796885153
772  22937665553573913575060
773  23921271165205191165035
774  24946439737712607009809
775  26014901971220947476427
776  27128459586630862091516
777  28288988197476264129022
778  29498440296925510684708
779  30758848363080263344901
780  32072328088614681429178
781  33441081738207213582988
782  34867401640233931793084
783  36353673816499146963834
784  37902381756929495941522
785  39516110343358230661487
786  41197549929816246864137
787  42949500583837012094735
788  44774876496718238454667
789  46676710567659528603587
790  48658159170283476028884
791  50722507106906102700176
792  52873172759669760175796
793  55113713444388057377203
794  57447830976866073247720
795  59879377458068895657248
796  62412361288599337053349
797  65050953419424752266307
798  67799493850062204771707
799  70662498381775285702977
800  73644665637795269851602
801  76750884358783269699001
802  79986240986408276798800
803  83356027543975509339006
804  86865749827905091457982
805  90521135919771540864582
806  94328145033697330480381
807  98292976709649724378918
808  102422080368500157075505
809  106722165240302174831478
810  111200210682791153984154
811  115863476902541634778436
812  120719516097013696103349
813  125776184030982494260066
814  131041652066900682708581
815  136524419663831253111640
816  142233327365915324397687
817  148177570296247130222770
818  154366712178639792982520
819  160810699904486962187377
820  167519878668834470077423
821  174505007694306222538802
822  181777276568748537592948
823  189348322216790319026354
824  197230246533062301604618
825  205435634698948466493192
826  213977574212629878796193
827  222869674656102376177791
828  232126088231093280764253
829  241761531089509160009895
830  251791305492664238142905
831  262231322827024948932828
832  273098127513215392718413
833  284408921838287919445437
834  296181591750681780222251
835  308434733650320104775115
836  321187682216143574721978
837  334460539306167578551316
838  348274203975447829045774
839  362650403649883505121865
840  377611726504555909572446
841  393181655087594727906161
842  409384601241826746320830
843  426245942368499269471769
844  443792059089151105174589
845  462050374353479418294188
846  481049394053373302290490
847  500818749194792998827055
848  521389239692064990676235
849  542792879840397427943872
850  565062945535908305622419
851  588234023303414389112144
852  612342061206341600055774
853  637424421703789587045530
854  663519936534551887042417
855  690668963698275531032456
856  718913446619401111929215
857  748296975569613135240132
858  778864851440708975408530
859  810664151949585831597917
860  843743800373981292031371
861  878154636907091303474308
862  913949492736921223756878
863  951183266945407981140148
864  989913006340917403838584
865  1030197988326594451928246
866  1072099806926486763271261
867  1115682462079923069981620
868  1161012452334991747186162
869  1208158871060212050364567
870  1257193506314820506620156
871  1308190944506027337875919
872  1361228677983943622089741
873  1416387216712495478275786
874  1473750204178055319184155
875  1533404537684819922946278
876  1595440493210499886178741
877  1659951854982870336700915
878  1727036049963446944538210
879  1796794287411222897992604
880  1869331703726357089392047
881  1944757512760065778368925
882  2023185161805227573192334
883  2104732493468268884445808
884  2189521913652526069726218
885  2277680565869037418369855
886  2369340512121790522499109
887  2464638920599915392869307
888  2563718260441903256524276
889  2666726503822113121007861
890  2773817335644015589653567
891  2885150371109532069363287
892  3000891381469697413332829
893  3121212528246522993171558
894  3246292606253576898482277
895  3376317295727202664335945
896  3511479423919802555100754
897  3651979236490787452073685
898  3798024679072264945197941
899  3949831689370505555314544
900  4107624500207764875890782
901  4271635953892823325332233
902  4442107828354323788397942
903  4619291175454610804218189
904  4803446671949792582908784
905  4994844983545240292495404
906  5193767142546178354184947
907  5400504939586415776661116
908  5615361329971262627043661
909  5838650855154009826674205
910  6070700079921039522572166
911  6311848045843947426131209
912  6562446741615588275739932
913  6822861590870296037733740
914  7093471958150058793173308
915  7374671673661843494803446
916  7666869577535959163839042
917  7970490084278894593606510
918  8285973768182098451154224
919  8613777970431912132525656
920  8954377428737423551987252
921  9308264930277013509176809
922  9675951988839648087356870
923  10057969547021311786013527
924  10454868704416188518831888
925  10867221472726960166258299
926  11295621558801958621835847
927  11740685176592179423959053
928  12203051889108920952075389
929  12683385481448696058146544
930  13182374866044455131138162
931  13700735021288762981465972
932  14239207964771866329190169
933  14798563762365028906689235
934  15379601574481989142935479
935  15983150740839804214456862
936  16610071905148300460525386
937  17261258181146870264178589
938  17937636361521107501922103
939  18640168171222556620462843
940  19369851566834734193719309
941  20127722083620797696911438
942  20914854232014604432863982
943  21732362945310736259777123
944  22581405080442297897081423
945  23463180973730941766037797
946  24378936053634070263657052
947  25329962512511841925754356
948  26317601039584794092359674
949  27343242617252835920226679
950  28408330383102694156315468
951  29514361559933351593494882
952  30662889456293970382853295
953  31855525540034043608665677
954  33093941587539601022517654
955  34379871911337639013656525
956  35715115668934701823431158
957  37101539255767297107579310
958  38541078785335837309038018
959  40035742659609317683472916
960  41587614232992809690932220
961  43198854573169509675034525
962  44871705322345462888207211
963  46608491662449289745635240
964  48411625388067826054442954
965  50283608090927784341437527
966  52227034459975063628070763
967  54244595701137995681243728
968  56339083081116055097207900
969  58513391599576195349337061
970  60770523794408763192137487
971  63113593684742108819257142
972  65545830856700228992703344
973  68070584696942073690908830
974  70691328779322738069169430
975  73411665410078821699231005
976  76235330337259199841975831
977  79166197630192974346877398
978  82208284735123763491007332
979  85365757713219223331853665
980  88642936667521646634459439
981  92044301365495227612778313
982  95574497064203299357425390
983  99238340545249469818878911
984  103040826367016339395973804
985  106987133341847911031826041
986  111082631246244962974258039
987  115332887772267886519638904
988  119743675728789501357626847
989  124320980501379477151506141
990  129071007780076385804776146
991  134000191564457567344747908
992  139115202455919415969296776
993  144422956247251131311547530
994  149930622820117177151947298
995  155645635361251747837573032
996  161575699908732363472068863
997  167728805239906829266323379
998  174113233113145218049276121
999  180737568875816240328225559