0 0
1 1
2 0
3 1
4 2
5 3
6 3
7 6
8 7
9 12
10 15
11 22
12 27
13 40
14 49
15 68
16 87
17 116
18 145
19 193
20 239
21 311
22 387
23 494
24 611
25 776
26 952
27 1193
28 1464
29 1817
30 2214
31 2733
32 3315
33 4060
34 4911
35 5974
36 7195
37 8713
38 10448
39 12585
40 15048
41 18039
42 21486
43 25660
44 30462
45 36231
46 42888
47 50820
48 59972
49 70843
50 83354
51 98143
52 115183
53 135212
54 158265
55 185287
56 216336
57 252596
58 294247
59 342701
60 398295
61 462813
62 536711
63 622232
64 720121
65 833066
66 962176
67 1110842
68 1280533
69 1475480
70 1697770
71 1952557
72 2242716
73 2574696
74 2952235
75 3383369
76 3873150
77 4431394
78 5064792
79 5785598
80 6602396
81 7530404
82 8580845
83 9772396
84 11119594
85 12645620
86 14368927
87 16318237
88 18517228
89 21001146
90 23800139
91 26957846
92 30512193
93 34517039
94 39020363
95 44088243
96 49781083
97 56180333
98 63361380
99 71424460
100 80463939
101 90602563
102 101958011
103 114681070
104 128917634
105 144852563
106 162666956
107 182586702
108 204835952
109 229691129
110 257428422
111 288385620
112 322903187
113 361392704
114 404272854
115 452045522
116 505223884
117 564419026
118 630259784
119 703488624
120 784874570
121 875319758
122 975762157
123 1087296531
124 1211066330
125 1348397524
126 1500681625
127 1669524314
128 1856615340
129 2063896658
130 2293418638
131 2547526267
132 2828703743
133 3139781251
134 3483763140
135 3864061313
136 4284306196
137 4748605142
138 5261339062
139 5827449469
140 6452214678
141 7141573209
142 7901878982
143 8740259795
144 9664354884
145 10682713183
146 11804506615
147 13039978161
148 14400130074
149 15897220898
150 17544433303
151 19356426866
152 21348977445
153 23539598608
154 25947152614
155 28592540630
156 31498291257
157 34689328737
158 38192530563
159 42037590827
160 46256547309
161 50884741816
162 55960325272
163 61525328211
164 67625134626
165 74309684980
166 81632921498
167 89654128571
168 98437360893
169 108052939751
170 118576855557
171 130092450454
172 142689800201
173 156467592488
174 171532505444
175 188001308188
176 206000228892
177 225667318371
178 247151818351
179 270616805492
180 296238584152
181 324209648924
182 354738099695
183 388050978955
184 424393727584
185 464033925848
186 507260827230
187 554389558368
188 605760736271
189 661745205047
190 722743769165
191 789192514950
192 861562714676
193 940366812872
194 1026158522362
195 1119539584724
196 1221160111987
197 1331726197085
198 1452000585165
199 1582811251690
200 1725052448221
201 1879694402755
202 2047784828658
203 2230459866799
204 2428946183665
205 2644573327042
206 2878776500299
207 3133110552479
208 3409253569302
209 3709022682476
210 4034378669688
211 4387443836565
212 4770507776010
213 5186047639619
214 5636735280097
215 6125460195677
216 6655338345596
217 7229738139754
218 7852291180434
219 8526921755778
220 9257859854464
221 10049674593886
222 10907289947585
223 11836022657358
224 12841601081988
225 13930208257340
226 15108504404028
227 16383675786713
228 17763461541579
229 19256209143548
230 20870906202727
231 22617243506916
232 24505652606963
233 26547377411540
234 28754518556923
235 31140114745564
236 33718194909692
237 36503870702223
238 39513397701756
239 42764280516589
240 46275344518401
241 50066855312021
242 54160602551997
243 58580035833795
244 63350362472382
245 68498701985683
246 74054200056833
247 80048204185448
248 86514396194889
249 93488992049729
250 101010895727201
251 109121926417622
252 117866997057397
253 127294372688634
254 137455877217714
255 148407187307241
256 160208071559960
257 172922724686567
258 186620043999371
259 201374009385372
260 217264002438586
261 234375238608755
262 252799135204259
263 272633802690260
264 293984468761753
265 316964036865392
266 341693574269787
267 368302947079979
268 396931381500038
269 427728185554132
270 460853394123385
271 496478589142217
272 534787640121347
273 575977636280455
274 620259736076131
275 667860226183448
276 719021495517584
277 774003238170475
278 833083569152850
279 896560390802564
280 964752670028041
281 1038001989888919
282 1116674010942566
283 1201160232805488
284 1291879664810708
285 1389280825780690
286 1493843652842479
287 1606081770895974
288 1726544672444128
289 1855820292639542
290 1994537496869551
291 2143369002134209
292 2303034214282942
293 2474302541260061
294 2657996627617820
295 2854996111401404
296 3066241309259718
297 3292737475655667
298 3535558999229004
299 3795854230006468
300 4074850255807769
301 4373858371956429
302 4694279514841021
303 5037610458443571
304 5405449992556382
305 5799505940568681
306 6221602181415818
307 6673686595560534
308 7157839041784652
309 7676280352208887
310 8231381389767935
311 8825673227707705
312 9461857429988411
313 10142817568353123
314 10871630885245524
315 11651581321229426
316 12486172740827908
317 13379143663989165
318 14334482258493927
319 15356442994094048
320 16449563629952291
321 17618684037882710
322 18868965442707775
323 20205911690883616
324 21635391034478539
325 23163660156595728
326 24797388825081419
327 26543687025368986
328 28410132851474889
329 30404803139313728
330 32536305008836089
331 34813810440302086
332 37247091931666012
333 39846561515469837
334 42623311053922938
335 45589156254162696
336 48756682188596390
337 52139292935703115
338 55751262984320956
339 59607793204672270
340 63725068877176982
341 68120322783174432
342 72811900690301762
343 77819332449722437
344 83163405870358880
345 88866246818070278
346 94951402525825104
347 101443931809577240
348 108370498989573089
349 115759475473858158
350 123641045606855287
351 132047321023407988
352 141012459901278340
353 150572795655987327
354 160766971253022509
355 171636084003915218
356 183223836791451228
357 195576700939567011
358 208744086428902328
359 222778525047240770
360 237735861922629236
361 253675461426121123
362 270660422625770867
363 288757810708990364
364 308038899272736668
365 328579430359488647
366 350459886846867208
367 373765784559884155
368 398587978408069482
369 425022990447532866
370 453173353847376957
371 483147981229856582
372 515062551031168701
373 549039920959698284
374 585210561851476057
375 623713021656604104
376 664694412491218323
377 708310931193624270
378 754728405944702735
379 804122880144206692
380 856681225713987580
381 912601797834293383
382 972095122876962045
383 1035384632416379273
384 1102707434666873821
385 1174315137163159410
386 1250474711603860070
387 1331469415687150514
388 1417599762412797147
389 1509184552768008592
390 1606561961820546508
391 1710090695302406240
392 1820151206245842133
393 1937146990017035440
394 2061505946833233313
395 2193681831466689521
396 2334155778745219734
397 2483437926009626637
398 2642069120656032961
399 2810622735501081488
400 2989706579607433173
401 3179964929007260446
402 3382080664478691128
403 3596777542639067087
404 3824822587030238102
405 4067028627438508168
406 4324256973645231773
407 4597420253984874595
408 4887485404448150530
409 5195476841003502177
410 5522479800432399072
411 5869643884841625037
412 6238186794721185044
413 6629398288399786333
414 7044644352379660836
415 7485371623300153144
416 7953112045661737697
417 8449487809203747287
418 8976216549755311002
419 9535116860851778503
420 10128114099691979879
421 10757246538396960312
422 11424671843968539589
423 12132673941891595317
424 12883670246672842617
425 13680219318571809382
426 14525028929819765420
427 15420964604242516050
428 16371058613696992903
429 17378519500301888696
430 18446742108106535003
431 19579318198666788670
432 20780047634572547570
433 22052950211336212926
434 23402278122261294496
435 24832529143161242307
436 26348460522311860084
437 27955103669517536690
438 29657779630686148873
439 31462115449390622040
440 33374061403086416712
441 35399909223732732247
442 37546311292048800093
443 39820300924136045751
444 42229313741620087034
445 44781210253792000843
446 47484299645212494626
447 50347364907877509337
448 53379689314143264847
449 56591084381056559799
450 59991919325539950240
451 63593152173624254411
452 67406362526988653047
453 71443786163678105265
454 75718351480683642761
455 80243717970142737551
456 85034316742003417337
457 90105393301103544227
458 95473052597462962544
459 101154306575405815705
460 107167124247140688965
461 113530484535662816278
462 120264431920463788851
463 127390135151870797310
464 134929949076478660734
465 142907479862374133576
466 151347653676827081916
467 160276789130093780093
468 169722673549647712428
469 179714643425671805482
470 190283669105329820601
471 201462444106347492555
472 213285479142343604003
473 225789201262847790190
474 239012058217341833430
475 252994628481610361550
476 267779737074794405900
477 283412577644064390382
478 299940840966742430876
479 317414850388974011795
480 335887704374924997868
481 355415426731652300448
482 376057124710738904510
483 397875155602188073050
484 420935302052052157512
485 445306956774300050901
486 471063316922483469654
487 498281588851793053856
488 527043203575206060286
489 557434043710038996016
490 589544682261216238109
491 623470634109412903410
492 659312620598021244629
493 697176848165618255929
494 737175301471038983074
495 779426052043645621341
496 824053582965125808543
497 871189130709365675807
498 920971044712767677487
499 973545165904289007423
500 1029065224841077583974
501 1087693260791415397473
502 1149600062492574494886
503 1214965632048297343583
504 1283979672784417008745
505 1356842102661868017656
506 1433763594166590699959
507 1514966142422858575348
508 1600683662561604453701
509 1691162618251440442273
510 1786662682548364102423
511 1887457433148179202117
512 1993835083335587047859
513 2106099250907037649046
514 2224569766514156976864
515 2349583523916146621726
516 2481495373757377208745
517 2620679063589816039391
518 2767528225944071823705
519 2922457417421903337199
520 3085903210821491994992
521 3258325343545501505156
522 3440207924532857348271
523 3632060703267643341901
524 3834420403359946353506
525 4047852124584250949387
526 4272950816150771610175
527 4510342825459007345899
528 4760687525418950869340
529 5024679024987331429547
530 5303047966346715489855
531 5596563413810773264176
532 5906034838261447650603
533 6232314202678585519621
534 6576298152984907203701
535 6938930320289302936305
536 7321203739211490478018
537 7724163388943083348053
538 8148908862235479299238
539 8596597169595897613721
540 9068445684441419566345
541 9565735237177917871822
542 10089813364570260165142
543 10642097723121304631874
544 11224079673505230905282
545 11837328045594455062418
546 12483493091873806586827
547 13164310639680677727289
548 13881606450888555165505
549 14637300800457382146284
550 15433413283374790830939
551 16272067862489564211661
552 17155498167759196744841
553 18086053060592683500524
554 19066202474908155606313
555 20098543549877938788609
556 21185807067187919937060
557 22330864209197264494245
558 23536733652153002515191
559 24806589012392370643487
560 26143766661146887259718
561 27551773927574043290353
562 29034297707234472257114
563 30595213497493153073418
564 32238594878824983307378
565 33968723465530464290719
566 35790099346777934806117
567 37707452043696407632585
568 39725752005561680981705
569 41850222673226884348905
570 44086353135174974033576
571 46439911406999601112482
572 48916958362255012863235
573 51523862348386419917917
574 54267314518494541832842
575 57154344915823566836780
576 60192339344813268117920
577 63389057069080354028401
578 66752649373556556597793
579 70291679034950458852745
580 74015140741475282001690
581 77932482510167672055429
582 82053628146813720413621
583 86389000801354281353090
584 90949547668252757595689
585 95746765889669833208287
586 100792729715825002662481
587 106100118985826275783100
588 111682248988715094018040
589 117553101773951974673130
590 123727358976971456043925
591 130220436235530467816542
592 137048519268922552317776
593 144228601702885964772843
594 151778524719337224422723
595 159717018621522890500741
596 168063746401452655653286
597 176839349408693356484031
598 186065495215853293473753
599 195764927789111371197821
600 205961520068390306932906
601 216680329075663511854628
602 227947653666142525063229
603 239791095051909208678264
604 252239620223846080544928
605 265323628413528739045324
606 279075020733088318222650
607 293527273147926293847403
608 308715512933588586750670
609 324676598786120956754179
610 341449204751761325006462
611 359073908161062968733023
612 377593281749218175347415
613 397051990164901608610780
614 417496891066807187041565
615 438977141029009203343786
616 461544306473352376513637
617 485252479870542873154080
618 510158401448952158044798
619 536321586675233520341515
620 563804459768508518955766
621 592672493536709135132270
622 622994355821693099211452
623 654842062868448046602142
624 688291139932170480766786
625 723420789467711514865148
626 760314067244861708297473
627 799058066765811339804468
628 839744112360691028486489
629 882467961372281507259384
630 927330015841226216844302
631 974435544140757615995757
632 1023894913010966621909239
633 1075823830483003683730732
634 1130343600185498743174665
635 1187581387568731517385554
636 1247670498584981815286990
637 1310750671409836996501068
638 1376968381793263016791556
639 1446477162678933078491140
640 1519437938735612169392453
641 1596019376497679123765055
642 1676398250818607276616026
643 1760759828398378553984293
644 1849298269154156755065271
645 1942217046264868230552821
646 2039729385730493241544763
647 2142058726352684292038106
648 2249439201055500734353366
649 2362116140535698743646544
650 2480346600246441436969914
651 2604399911794156361173712
652 2734558259845202309700336
653 2871117285720488361941376
654 3014386718875915301263758
655 3164691037554045900486705
656 3322370159915241160360024
657 3487780167050565494427645
658 3661294059305037005062301
659 3843302547440906663927822
660 4034214880200739933913494
661 4234459709938775646026180
662 4444485998023352756270996
663 4664763961830089236751773
664 4895786065184485917238974
665 5138068054238361040647756
666 5392150040808673928852192
667 5658597635342565948033845
668 5938003131722300962077280
669 6230986746269350722838287
670 6538197913363011680253033
671 6860316640245614209987709
672 7198054923649456254393092
673 7552158231049261352436754
674 7923407049414664320925008
675 8312618504518846017194651
676 8720648053938539296456221
677 9148391257076230944506322
678 9596785625623720896587591
679 10066812558096903548863374
680 10559499362170123365957992
681 11075921368765471665291558
682 11617204141962025977874561
683 12184525789034667994441618
684 12779119375053987855579028
685 13402275446742450190493780
686 14055344670417294903286006
687 14739740589134878184562331
688 15456942504301176114207510
689 16208498487319627101791462
690 16996028527013639016142326
691 17821227818891551381028291
692 18685870202505665253185161
693 19591811753513367706053540
694 20540994537251547596128890
695 21535450531019960676059557
696 22577305722493547483826149
697 23668784392098481783787880
698 24812213587434238560277053
699 26010027798271513074822776
700 27264773840928663207844272
701 28579115961312313622867625
702 29955841166208289581309038
703 31397864792930308050703238
704 32908236327764638247565096
705 34490145484211605929137944
706 36146928552388644363838773
707 37882075031567022209065718
708 39699234558214289303723665
709 41602224142570308190269962
710 43595035727224035379350221
711 45681844081866379191408767
712 47867015048876730354442301
713 50155114155165518405562180
714 52550915606224294384120647
715 55059411679160793672604113
716 57685822532076701776556472
717 60435606448037979785924136
718 63314470532523603536631735
719 66328381884202276070624776
720 69483579259583408989170128
721 72786585253129773018174373
722 76244219015182134534802421
723 79863609531171008154507514
724 83652209486425657697275327
725 87617809742105824186075434
726 91768554448695165728683546
727 96112956824808650549127476
728 100659915630065121830185946
729 105418732362195405182083725
730 110399129209648335960822831
731 115611267792490768275925353
732 121065768725590871907581137
733 126773732039731576692853924
734 132746758497604413245776348
735 138996971843425525366197785
736 145537042026338821991167771
737 152380209439707663483280121
738 159540310219949956998395533
739 167031802650664675081919228
740 174869794719492949670500319
741 183070072877419526891415378
742 191649132052069489337079079
743 200624206969001100293346907
744 210013304837012100967646333
745 219835239456120993123074848
746 230109666809083167761946493
747 240857122200160357065166908
748 252099059007257774400300049
749 263857889116633812906393822
750 276157025111997653415547042
751 289020924293151413560823527
752 302475134602177000861359720
753 316546342538780316926688737
754 331262423149502034980098538
755 346652492179409944165435453
756 362746960478259143778852663
757 379577590757329295080367806
758 397177556796817616744217577
759 415581505208232196925161659
760 434825619860223280214941410
761 454947689081226934248608870
762 475987175756639731028544542
763 497985290443580829877930233
764 520985067631023043341342422
765 545031445278845817643358580
766 570171347774501495854268359
767 596453772452226405199489100
768 623929879825314944199774935
769 652653087688721900664583152
770 682679169255330901055759299
771 714066355496521969352130853
772 746875441864270822942421392
773 781169899579900087569547401
774 817015991681773566296920705
775 854482894032752754084010247
776 893642821496025007687508534
777 934571159497133241795739710
778 977346601198498389635908976
779 1022051290522694806449301418
780 1068770971269927455531879563
781 1117595142585937705038468459
782 1168617221046541252053744068
783 1221934709636654172872013808
784 1277649373912493493778097037
785 1335867425648236346763541739
786 1396699714280176925341059473
787 1460261926475039662090136796
788 1526674794161863785816844913
789 1596064311381597636839737499
790 1668561960322382504516584406
791 1744304946924422061640845475
792 1823436446453349327550880847
793 1906105859458208677280507479
794 1992469078546457844867881368
795 2082688766426993614191661622
796 2176934645689868845260456316
797 2275383800811472563277042637
798 2378220992893098768258743730
799 2485638987662560142957099793
800 2597838897289269353488324995
801 2715030536586698371065676966
802 2837432794198637829006329724
803 2965274019391064559050186256
804 3098792425095825275929770688
805 3238236507879781301450132824
806 3383865485539501965489932674
807 3535949753051246562461314334
808 3694771357634627500262345157
809 3860624493720392425668846998
810 4033816018643806395826631594
811 4214665989919744876634421302
812 4403508224989237136414399632
813 4600690884364620747932107666
814 4806577079136892760441560248
815 5021545503849278929204109875
816 5245991095780490707457525354
817 5480325721724831104704269299
818 5724978893399027857802391806
819 5980398512652879288447686342
820 6247051647707049701755960646
821 6525425341692354116750382921
822 6816027454814943984820131841
823 7119387541526907088337862228
824 7436057764135996067134098836
825 7766613844347726624113114710
826 8111656054291750637173950567
827 8471810248648713250145379276
828 8847728939557290127363618522
829 9240092416050562007042940081
830 9649609909839582275913573676
831 10077020809337021092906815634
832 10523095923888098920873206490
833 10988638800257058911343031701
834 11474487093497840102334614437
835 11981513994425135333675144510
836 12510629715989001643267407778
837 13062783040950712175714986882
838 13638962933351620473757187515
839 14240200216368882827252785264
840 14867569319253632325625405263
841 15522190096157424151592690188
842 16205229719762798609932295729
843 16917904652752829657534636887
844 17661482700273493635248876913
845 18437285146671204160644868974
846 19246688979916478970627470571
847 20091129207263454521454908814
848 20972101265834005695518175993
849 21891163531965023917423368628
850 22849939933307699243197721325
851 23850122667829363903750386434
852 24893475034030891668090323561
853 25981834376867212964459014990
854 27117115154034050963530799247
855 28301312127472413670277400878
856 29536503685132069682169517134
857 30824855298238618473347645514
858 32168623119513726038856852021
859 33570157728017606847168230541
860 35031908026504267640535870797
861 36556425297416930203291722152
862 38146367423890260579094682721
863 39804503282381687736011177433
864 41533717313812483131026776003
865 43337014280375149921972142916
866 45217524215442748307894668935
867 47178507574313463887613874693
868 49223360593825121289372821247
869 51355620869195532278397574585
870 53578973156770035084824003204
871 55897255411704109997713163598
872 58314465069960386292204076567
873 60834765584373201470069744584
874 63462493224913302702727123873
875 66202164153688572309865105285
876 69058481785626280607103932162
877 72036344446217399539289559296
878 75140853338145687525042444176
879 78377320829093492472362220129
880 81751279073493497398412575776
881 85268488981501733890964926277
882 88934949548982307497012679978
883 92756907562840105845235750815
884 96740867696593672198616267504
885 100893603011669060772539412780
886 105222165880495373438929346216
887 109733899348117434872465951031
888 114436448949688340179539959320
889 119337775001889060817850481433
890 124446165387020649933055748231
891 129770248849252577781863130719
892 135319008823264128304063348241
893 141101797816311452085981335964
894 147128352365565586674815757441
895 153408808593424546358201491817
896 159953718384379211132554115241
897 166774066207937454387273672532
898 173881286613056435753141710909
899 181287282420529770463716517539
900 189004443640795957604327186133
901 197045667145708858196673641783
902 205424377123910599651537982603
903 214154546350605285626102596198
904 223250718303717556995673268103
905 232728030159668069557603305200
906 242602236703276337300716300195
907 252889735187646337970970553376
908 263607591181268516859178200225
909 274773565441021134910636630421
910 286406141851239683535281513969
911 298524556470584758001921073361
912 311148827730040358094722731416
913 324299787827057215346713293020
914 337999115362582012661626543135
915 352269369269526205727724995611
916 367134024083088673425508929752
917 382617506605299431192672143221
918 398745234018156694730639012343
919 415543653501833451928881187501
920 433040283416590350722708359420
921 451263756109297951729629417764
922 470243862407799535778192840775
923 490011597868786641307575547484
924 510599210847367930749618731463
925 532040252459141017164115872591
926 554369628508279343752894847847
927 577623653457977591575871500728
928 601840106522510378055600771253
929 627058289963208119023895783172
930 653319089673789940140459577222
931 680665038143776891225094646139
932 709140379892086549267830619859
933 738791139466445489880607865943
934 769665192107894133347798082903
935 801812337183464990588293268092
936 835284374494033306597936363634
937 870135183568437270420152137510
938 906420806059184108750012748355
939 944199531359470265155579206217
940 983531985565787007974476515255
941 1024481223915132116169397141631
942 1067112826830739948268127900400
943 1111494999715354403135095035343
944 1157698676636335803656548951941
945 1205797628052395209932678432741
946 1255868572737419373702768559792
947 1307991294062771705516012260995
948 1362248760805557939668598596172
949 1418727252656718625881636331188
950 1477516490609380188239605974157
951 1538709772414754968217944431125
952 1602404113299951698042351451981
953 1668700392149438227809017303710
954 1737703503359508505532567912771
955 1809522514583047060754718426447
956 1884270830590074092439039099476
957 1962066363478098464144870201529
958 2043031709475118966341648252125
959 2127294332587306550568626304280
960 2214986755352883260573087434973
961 2306246756973602607509169748619
962 2401217579105439336815012396097
963 2500048139600734355012639763928
964 2602893254505017894060991169163
965 2709913868623176580237390245043
966 2821277294981439404708583976690
967 2937157463523965049829225759336
968 3057735179395516561379316152707
969 3183198391174946209824289506381
970 3313742469437877895219538762720
971 3449570496041209979355935644698
972 3590893564536758602927328003943
973 3737931092136670127506244257957
974 3890911143669038141277641576985
975 4050070767978621946645785499389
976 4215656347244562492181933979344
977 4387923959704691795417675735193
978 4567139756294311881333275634217
979 4753580351726349946427585734975
980 4947533230559452567539530826014
981 5149297168821041800879179387398
982 5359182671773490433101368985237
983 5577512428433568985857213566489
984 5804621783478039459304230831805
985 6040859227191915179443656227030
986 6286586904140334151553016376553
987 6542181141270408782434521288736
988 6808032996175674815066541153574
989 7084548826283079816564443609109
990 7372150879750679000383907902919
991 7671277908893566210722045998885
992 7982385806985908202249395644136
993 8305948269318503703698388730939
994 8642457479423897932544295294406
995 8992424821414991633357343585399
996 9356381619418129138711024133332
997 9734879905118086920850569815474
998 10128493214470045332755469546301
999 10537817414672777903174589667526
1000 10963471562537762198588896679697