0 1
1 0
2 2
3 2
4 4
5 5
6 9
7 11
8 18
9 23
10 34
11 44
12 63
13 80
14 111
15 142
16 190
17 242
18 319
19 402
20 522
21 655
22 837
23 1045
24 1322
25 1638
26 2053
27 2532
28 3144
29 3857
30 4757
31 5803
32 7111
33 8636
34 10516
35 12716
36 15404
37 18543
38 22355
39 26807
40 32168
41 38430
42 45929
43 54670
44 65088
45 77220
46 91599
47 108330
48 128077
49 151006
50 177974
51 209242
52 245872
53 288285
54 337813
55 395052
56 461702
57 538607
58 627889
59 730754
60 849867
61 986858
62 1145118
63 1326848
64 1536287
65 1776427
66 2052592
67 2368727
68 2731566
69 3146299
70 3621358
71 4163582
72 4783546
73 5490111
74 6296594
75 7214453
76 8260327
77 9449036
78 10801392
79 12336349
80 14079990
81 16056501
82 18298404
83 20836541
84 23711446
85 26962166
86 30639265
87 34792068
88 39483398
89 44775489
90 50746357
91 57474111
92 65055621
93 73588729
94 83193350
95 93991876
96 106132605
97 119768045
98 135081510
99 152262669
100 171537553
101 193141709
102 217353545
103 244464697
104 274817794
105 308773294
106 346751992
107 389198762
108 436629791
109 489592785
110 548720350
111 614685697
112 688262699
113 770277675
114 861676193
115 963470414
116 1076814462
117 1202946279
118 1343272315
119 1499304598
120 1672755038
121 1865467156
122 2079522421
123 2317165380
124 2580923171
125 2873525093
126 3198035840
127 3557768955
128 3956436997
129 4398057565
130 4887122130
131 5428495974
132 6027606785
133 6690338127
134 7423242072
135 8233424893
136 9128786299
137 10117899412
138 11210278495
139 12416253080
140 13747270071
141 15215760968
142 16835482247
143 18621378645
144 20589965008
145 22759186321
146 25148849035
147 27780477388
148 30677800118
149 33866607681
150 37375299610
151 41234744469
152 45478899152
153 50144672485
154 55272625377
155 60906845141
156 67095734942
157 73891903107
158 81353057792
159 89541914522
160 98527209713
161 108383637516
162 119192995676
163 131044159720
164 144034384002
165 158269320890
166 173864497619
167 190945397778
168 209649135228
169 230124612466
170 252534424766
171 277055110033
172 303879314695
173 333216162330
174 365293714468
175 400359482975
176 438683234210
177 480557671735
178 526301631750
179 576260978660
180 630812243471
181 690363773965
182 755359887478
183 826282320985
184 903654971226
185 988045711434
186 1080071798466
187 1180402124232
188 1289763395676
189 1408942896322
190 1538795550039
191 1680247296184
192 1834303159804
193 2002051349758
194 2184672492739
195 2383444576597
196 2599753516463
197 2835099103912
198 3091107092759
199 3369536326957
200 3672292580961
201 4001437061384
202 4359202256824
203 4748002060537
204 5170449915605
205 5629370829738
206 6127822166275
207 6669107857710
208 7256802227687
209 7894766782728
210 8587177499117
211 9338544612787
212 10153743894847
213 11038039916786
214 11997121894876
215 13037131009670
216 14164701475089
217 15386992558720
218 16711735657238
219 18147271752388
220 19702605364893
221 21387448325627
222 23212281595629
223 25188406339353
224 27328014776246
225 29644249680022
226 32151285568112
227 34864397956208
228 37800056367311
229 40976004839463
230 44411368489027
231 48126746977047
232 52144336578155
233 56488038606094
234 61183599202893
235 66258734982973
236 71743293118868
237 77669396777278
238 84071628406458
239 90987197960639
240 98456152687965
241 106521571533890
242 115229805246954
243 124630700820667
244 134777876228816
245 145728979376389
246 157546002360053
247 170295579990418
248 184049349219200
249 198884292992979
250 214883151225728
251 232134816624503
252 250734804448701
253 270785707832092
254 292397734643132
255 315689230858127
256 340787293928767
257 367828374033255
258 396958974624781
259 428336342694676
260 462129268721527
261 498518878596438
262 537699546799405
263 579879804471056
264 625283381497723
265 674150247139817
266 726737798931965
267 783322054495019
268 844199007511713
269 909685991995079
270 980123228302852
271 1055875383952114
272 1137333335836844
273 1224915954910488
274 1319072114201568
275 1420282728493940
276 1529063041659446
277 1645964956571273
278 1771579639871486
279 1906540182040760
280 2051524562699025
281 2207258686230270
282 2374519756390503
283 2554139738839548
284 2747009200427718
285 2954081256766977
286 3176375938767331
287 3414984691233277
288 3671075337405142
289 3945897203168726
290 4240786759803213
291 4557173458158293
292 4896586140182474
293 5260659678669017
294 5651142259898582
295 6069902936934178
296 6518939899212258
297 7000389061393841
298 7516533450628287
299 8069812969032569
300 8662835046201617
301 9298385731144924
302 9979441776868940
303 10709183237676766
304 11491007173956200
305 12328541953650343
306 13225662789451766
307 14186507968634893
308 15215496462252474
309 16317346336174826
310 17497094702282732
311 18760118596123876
312 20112157574376310
313 21559337380711391
314 23108195532696044
315 24765708138223173
316 26539318858260167
317 28436969282413287
318 30467131702619693
319 32638843507817140
320 34961744258773901
321 37446114619692744
322 40102918285702782
323 42943846034623323
324 45981363127614543
325 49228759137168794
326 52700201519283523
327 56410791955620896
328 60376626882322295
329 64614861176625844
330 69143776524891039
331 73982853386890126
332 79152848195408843
333 84675874646991119
334 90575490847878256
335 96876791110082188
336 103606504295760207
337 110793097442556525
338 118466886712975155
339 126660154335619137
340 135407273738368667
341 144744841475003718
342 154711818314058846
343 165349678024237739
344 176702566407631271
345 188817469045812932
346 201744390507896120
347 215536543415614010
348 230250550327451555
349 245946656766978869
350 262688958587940433
351 280545641930200049
352 299589239209273160
353 319896899323006420
354 341550675787861661
355 364637830919496646
356 389251160062423144
357 415489333915045298
358 443457263272382705
359 473266484166959677
360 505035568073089881
361 538890555093346458
362 574965415164537663
363 613402535143360417
364 654353237213623182
365 697978326422342603
366 744448673224275675
367 793945828797198792
368 846662679482971241
369 902804138078778123
370 962587878851095666
371 1026245113969392465
372 1094021418792908430
373 1166177603693562017
374 1242990640458311265
375 1324754640953135639
376 1411781896756570527
377 1504403977461659764
378 1602972897075637815
379 1707862346254416216
380 1819469000586806387
381 1938213902725640943
382 2064543929437597138
383 2198933341456761010
384 2341885428145290975
385 2493934244967237857
386 2655646456794597271
387 2827623285207273103
388 3010502573915023424
389 3204960970661079643
390 3411716240942976974
391 3631529712157985038
392 3865208864826770028
393 4113610069803118509
394 4377641489563934192
395 4658266142850852254
396 4956505152328407023
397 5273441174966620980
398 5610222036529445272
399 5968064570391824216
400 6348258683944622198
401 6752171653417194720
402 7181252672426978874
403 7637037655798528633
404 8121154326204068748
405 8635327585994928123
406 9181385204231559187
407 9761263822241043114
408 10377015310394001482
409 11030813480540338027
410 11724961189734799596
411 12461897840966563100
412 13244207319744602024
413 14074626373716537326
414 14956053477697086146
415 15891558192960996742
416 16884391067038828230
417 17937994084781024097
418 19056011721164145106
419 20242302608781367218
420 21500951875130322598
421 22836284165116975022
422 24252877408976376144
423 25755577353834070854
424 27349512924692091257
425 29040112436240674688
426 30833120727399979240
427 32734617243588394844
428 34751035145338183564
429 36889181472309308290
430 39156258448696626022
431 41559885963653017821
432 44108125320813509835
433 46809504295693999258
434 49673043603932357881
435 52708284824933196766
436 55925319893641572594
437 59334822211509747226
438 62948079500092836797
439 66777028455638917358
440 70834291339875048090
441 75133214573534651517
442 79687909480756983774
443 84513295260067548126
444 89625144344269325934
445 95040130235213021451
446 100775877991379742797
447 106851017465709832377
448 113285239488763221181
449 120099355107457315400
450 127315358093311711794
451 134956490844755898389
452 143047313918142833289
453 151613779327983806136
454 160683307873821639058
455 170284870652053942218
456 180449075035151704401
457 191208255296421025193
458 202596568190270311537
459 214650093688212965062
460 227406941210826915648
461 240907361580480353459
462 255193865068305986577
463 270311345787581191791
464 286307212843569644789
465 303231528522378640226
466 321137153969108778610
467 340079902671630734608
468 360118702244483154413
469 381315764866753753296
470 403736766917061536734
471 427451038201155161607
472 452531761368720429146
473 479056181961136613829
474 507105829745566748160
475 536766751828402967108
476 568129758268103515376
477 601290680737290775332
478 636350645025246631575
479 673416357993683459356
480 712600409855096694818
481 754021592456393344594
482 797805234523058542866
483 844083554623862671019
484 892996032905893259216
485 944689802445503801251
486 999320061368879633556
487 1057050506682544548747
488 1118053791081764664911
489 1182512003781963601267
490 1250617176766733116204
491 1322571817613450503381
492 1398589470428186369416
493 1478895306179061669980
494 1563726744111558585719
495 1653334105676566348600
496 1747981302821571349039
497 1847946562232259153728
498 1953523187558386729022
499 2065020361384060624069
500 2182763989177921434965
501 2307097587174250794474
502 2438383216642134956432
503 2577002466704434351815
504 2723357488407253638106
505 2877872082434257783917
506 3040992843434189599315
507 3213190363612560907071
508 3394960498850006879342
509 3586825700281366727780
510 3789336414921147234861
511 4003072558581647517292
512 4228645065024464967196
513 4466697514935874993166
514 4717907849056891425091
515 4982990169437928316263
516 5262696633577361461932
517 5557819445832066518883
518 5869192951329897083093
519 6197695837232869641155
520 6544253447097974405533
521 6909840213691843779813
522 7295482216573903340855
523 7702259870363113168939
524 8131310750626336944557
525 8583832563918763303197
526 9061086269598950842487
527 9564399360626266000249
528 10095169311714814935683
529 10654867202797120197435
530 11245041526996680325561
531 11867322191882916498822
532 12523424724113303225066
533 13215154687138564526356
534 13944412323069740509771
535 14713197429375545171496
536 15523614482599723657319
537 16377878020858270295755
538 17278318298503352208238
539 18227387225913803769675
540 19227664609112558217145
541 20281864703490011788487
542 21392843097774798861116
543 22563603943980722543460
544 23797307551052265173558
545 25097278359530473960089
546 26467013316695745563953
547 27910190671259519957308
548 29430679208963338112722
549 31032547950079745333865
550 32720076332259291984136
551 34497764901829468246492
552 36370346539276943051962
553 38342798244337352478320
554 40420353508931653523032
555 42608515305918541723653
556 44913069724651100903807
557 47340100284101052726169
558 49896002957552278910369
559 52587501942693256845924
560 55421666214413043961459
561 58405926897495044984444
562 61548095500133036111965
563 64856383049155068110216
564 68339420171846303411850
565 72006278169305695412241
566 75866491130573671281532
567 79930079136906804924359
568 84207572610198068500531
569 88710037859788716208648
570 93449103886886135106061
571 98436990506173393867638
572 103686537849537653275979
573 109211237317356726694900
574 115025264048527548534671
575 121143510981091810983667
576 127581624581493751272297
577 134356042321356725711386
578 141484031987315131048530
579 148983732910492839997003
580 156874199209377460333795
581 165175445141122525959068
582 173908492664017115408879
583 183095421315401401701638
584 192759420517607789973785
585 202924844426333241106231
586 213617269444791719454677
587 224863554529142507071419
588 236691904420327961502568
589 249131935939959511797773
590 262214747498279792354790
591 275972991965133592034040
592 290440953066082416263453
593 305654625469147143553996
594 321651798739745148981911
595 338472145345232919608059
596 356157312903499319712178
597 374751020874449101005801
598 394299161907281434530413
599 414849908061472766449017
600 436453822134554793261649
601 459163974335459402640117
602 483036064558592807111755
603 508128550520231367720854
604 534502782036531533552305
605 562223141729705660393431
606 591357192468033920192908
607 621975831853558730213676
608 654153454091963429130665
609 687968119588326042556167
610 723501732634759778606718
611 760840227566259234280526
612 800073763785196934159749
613 841296930066456039500147
614 884608958581266868356415
615 930113949090716339629884
616 977921103788101915377585
617 1028144973283701810946999
618 1080905714256034604885167
619 1136329359309732132478272
620 1194548099613143378437426
621 1255700580906654210389797
622 1319932213508404495079227
623 1387395496963949126503358
624 1458250360025037118480578
625 1532664516664744529206672
626 1610813838878003195451733
627 1692882747041042446269631
628 1779064618648514925635276
629 1869562216274203648550948
630 1964588135650200946636520
631 2064365274789486292502440
632 2169127325129880002248191
633 2279119285710579609017270
634 2394598001449936555427689
635 2515832726629863425872522
636 2643105714754487067258581
637 2776712835991236384126968
638 2916964223469958498954581
639 3064184949760439888689280
640 3218715734921734364298753
641 3380913687566094576271595
642 3551153080459427152485542
643 3729826162234637743868411
644 3917344006879972665296573
645 4114137402724440248288772
646 4320657782735316019424460
647 4537378198008764948859595
648 4764794336435326885607897
649 5003425588594663215120101
650 5253816163043131204013939
651 5516536253237648172100185
652 5792183258457652453927056
653 6081383061174784514522968
654 6384791363448214661754262
655 6703095085020019109543156
656 7037013825924116255261912
657 7387301396528212952424022
658 7754747418079049401036912
659 8140178996937507449020177
660 8544462475853714403785804
661 8968505265759843072362770
662 9413257761735689663291772
663 9879715346942010674438601
664 10368920488508972569786211
665 10881964929520429157926320
666 11419991981443383879759841
667 11984198921520048372325509
668 12575839499866207405107813
669 13196226561203687055727832
670 13846734786400183545153641
671 14528803559191287421068730
672 15243939963725792826368203
673 15993721918796036159958386
674 16779801454903829586905102
675 17603908140554012159320807
676 18467852664480951244825700
677 19373530580777463904696584
678 20322926224235511644176577
679 21318116803496880345318539
680 22361276679980776915536547
681 23454681840871073315587979
682 24600714574845938783971193
683 25801868359577753944536974
684 27060752970465162543334947
685 28380099820436246861533766
686 29762767541132613739040494
687 31211747816196136557989584
688 32730171477890870033389157
689 34321314878742539289355933
690 35988606550432142244813908
691 37735634162671382231582843
692 39566151795388833705035268
693 41484087538091872068322710
694 43493551430921626751950071
695 45598843762503267825082614
696 47804463740401536093572344
697 50115118550629716429735636
698 52535732823427919568122705
699 55071458523222751669158458
700 57727685281513272401528731
701 60510051192187368721175851
702 63424454089676165890023843
703 66477063331181861092157136
704 69674332105194512968798199
705 73023010289415618124714849
706 76530157882269590820561045
707 80203159033167602774231378
708 84049736697841688374431159
709 88077967946138469505645260
710 92296299950913080746227272
711 96713566687831098316482581
712 101339006377243534312909461
713 106182279700571271710990763
714 111253488825107547616772712
715 116563197272531522361626627
716 122122450668022867567964184
717 127942798408374641002300906
718 134036316289233774759419488
719 140415630133239359842894538
720 147093940462707505881593340
721 154085048262297448860701674
722 161403381879131034081310948
723 169064025109781119372977212
724 177082746525754105143183425
725 185476030091206277963445073
726 194261107129029980094087809
727 203455989693745838973128558
728 213079505412235938862638224
729 223151333855854690935888236
730 233692044510272087960627773
731 244723136412124802755951153
732 256267079524606164765299869
733 268347357927084414058899532
734 280988514897151737649664663
735 294216199966722805224727641
736 308057218037393689472139816
737 322539580643768063943561949
738 337692559457352112143670130
739 353546742127419166196381518
740 370134090559467242596408952
741 387488001736021565188540759
742 405643371189111242487845797
743 424636659238235432481820440
744 444505960112595901804051899
745 465291074081246521899202878
746 487033582720188319463414739
747 509776927450732536695431172
748 533566491489283370894289762
749 558449685354441550255552868
750 584476036083647738460926572
751 611697280317828279705025442
752 640167461419352813142608333
753 669943030795392389943486263
754 701082953606186812991476343
755 733648819045089593503374930
756 767704955385299555959698808
757 803318549996177063324005795
758 840559774540755389018694236
759 879501915574728673038191650
760 920221510776637940154980803
761 962798491048386578884160775
762 1007316328735444310813563047
763 1053862192226309337593979786
764 1102527107201878582864646494
765 1153406124816454129564459385
766 1206598497104117091470439518
767 1262207859916218128286331394
768 1320342423708735891299783983
769 1381115172511290622361954332
770 1444644071423683361554400946
771 1511052282999969684701796461
772 1580468392895330177655316598
773 1653026645166332319223640740
774 1728867187631697894158902932
775 1808136327717315451476523342
776 1890986799227126841072072270
777 1977578040499542167289602016
778 2068076484428409407270580857
779 2162655860847105844987011148
780 2261497511795294181046496454
781 2364790720209067765586585709
782 2472733052597920133856977158
783 2585530716294931528482557181
784 2703398931891152669886366559
785 2826562321490045651982004595
786 2955255313444459521215516281
787 3089722564265577855523320587
788 3230219398422089053178243814
789 3377012266777040748008307789
790 3530379224441027816626411609
791 3690610428852009698144116287
792 3858008658925808780441101846
793 4032889856155622904656040624
794 4215583688575417917601133013
795 4406434138539198105647772206
796 4605800115307687690148845407
797 4814056093474171987093783685
798 5031592778304028355218078323
799 5258817799106027636914465470
800 5496156431799777716871315751
801 5744052351890838399428791608
802 6002968419115121410721701929
803 6273387495065247544640495588
804 6555813295165718260630318334
805 6850771276419035059157294758
806 7158809562403517442961795276
807 7480499907063406636442299552
808 7816438698895249862787277620
809 8167248007199326609998284441
810 8533576672133462552920633964
811 8916101440376673155453108321
812 9315528148284257043981417509
813 9732592954491816633536494317
814 10168063624005905783538368556
815 10622740865901088349715541773
816 11097459726829944185893844770
817 11593091042641372660991913092
818 12110542950496351572460973673
819 12650762463966394943579289036
820 13214737113701382468659090353
821 13803496656357376828508511297
822 14418114854584707002064451457
823 15059711330989029225888967288
824 15729453499096631292213711411
825 16428558574476851759974648334
826 17158295669302643452437304708
827 17919987973761825138082505162
828 18715015027870094639823199533
829 19544815087379094264669870671
830 20410887587622548676836477452
831 21314795709297273315654371535
832 22258169050337674161797099812
833 23242706408208622782884043113
834 24270178677116470662396414625
835 25342431864817712778775494186
836 26461390233893787520159460222
837 27629059572554805015292958186
838 28847530600239191453972275583
839 30118982513486261802404781653
840 31445686677779356476297388930
841 32830010471284174174561371603
842 34274421286645287965225827562
843 35781490697249150339986365608
844 37353898794619385745634592115
845 38994438703875265694142021624
846 40706021284462408391900165045
847 42491680023651189357259086823
848 44354576130598784989066407233
849 46298003839080256237639805866
850 48325395927318565882219252407
851 50440329463677773722361504312
852 52646531787334090806558735511
853 54947886733400657608103766969
854 57348441112360345917820055123
855 59852411454051021710040855412
856 62464191026856346070683124660
857 65188357143176568320709000976
858 68029678762694988760455433832
859 70993124405410848740486274755
860 74083870386885775725535135053
861 77307309388642349645919093248
862 80669059377167635544268992521
863 84174972885505185721573410343
864 87831146671974178206441232957
865 91643931771127319241299023102
866 95619943952658392605061495902
867 99766074604588924063681559769
868 104089502057710230519141735436
869 108597703368924912502949397516
870 113298466581829917687352858899
871 118199903483604151457662310748
872 123310462878016956263814853062
873 128638944395151842576534125093
874 134194512859252794679873081959
875 139986713236940222252434381167
876 146025486188920814587586794072
877 152321184249221807323591662924
878 158884588656926611672938330264
879 165726926866366704130643369499
880 172859890762745762857262039337
881 180295655611227268719847610720
882 188046899768618333494193514281
883 196126825187921051574695027380
884 204549178747210926304302136785
885 213328274435530238127875047762
886 222479016429765920205028140316
887 232016923097806582558469772490
888 241958151964655717058218315570
889 252319525679607461916359688782
890 263118559024082192185990050916
891 274373487001260906474538085681
892 286103294050265164843289440745
893 298327744429292098545665633421
894 311067413813847735797964985177
895 324343722158015084866415463460
896 338178967868562809736957167779
897 352596363343634046435360489731
898 367620071929770445891958620774
899 383275246353111610716748015536
900 399588068682783045791121040729
901 416585791886733872122369407947
902 434296783042628048910908111678
903 452750568268816594245257051751
904 471977879442943383274834294526
905 492010702778349987085673119507
906 512882329331166737610772837947
907 534627407513793776893488316861
908 557281997693409310532044012747
909 580883628957178199982339981463
910 605471358128995479719438836352
911 631085831125871481336401427733
912 657769346745472168403931482035
913 685565922979854677349069897523
914 714521365954109254470698066827
915 744683341592418950014462293085
916 776101450118004121623951735341
917 808827303497513705756255929692
918 842914605944687153572398712778
919 878419237602523107429798756647
920 915399341527782468819021538629
921 953915414106407198916441230866
922 994030399033382557001726747726
923 1035809784995691746307264886614
924 1079321707202340136110970223085
925 1124637052910943092054225426285
926 1171829571106110560722914958650
927 1220975986490804148563536166021
928 1272156117958023728446296757313
929 1325453001716581327541946660660
930 1380953019251377133567252094269
931 1438746030305486129745726579340
932 1498925511078532873704801302704
933 1561588697843255999439377918584
934 1626836736189883786001411668879
935 1694774836115936832970802396832
936 1765512433187386151942875213955
937 1839163356005703565405186966560
938 1915846000224290944693419398273
939 1995683509367043773461153366414
940 2078803962711439752813610236888
941 2165340570508522450582785814552
942 2255431876822522633339344784161
943 2349221970283603224558862831183
944 2446860703058379555648575319096
945 2548503918354431589054972671773
946 2654313686787043431915422210533
947 2764458551948854164771853628294
948 2879113785536039846664059525749
949 2998461652398045555718167316910
950 3122691685891808420130625520988
951 3252000973935833433048442321607
952 3386594456174466391547162142189
953 3526685232678227842350155023507
954 3672494884622194612954760916391
955 3824253807401116319507391529574
956 3982201556657302696264663142531
957 4146587207715288361566109596833
958 4317669728935947796495205345888
959 4495718369522069295562134471137
960 4681013062327479273668275662605
961 4873844842242611813946530664260
962 5074516280751023488281251030555
963 5283341937273734366865910229440
964 5500648827941517696788823923873
965 5726776912459336980050336629626
966 5962079599752129462244664072850
967 6206924273107033346981033571697
968 6461692835554046368868667812399
969 6726782276254959742409296615405
970 7002605258699332853768509800821
971 7289590731536234573931998370658
972 7588184562901580826752594444671
973 7898850199133119477513610816096
974 8222069348798562273931730995831
975 8558342692997014245272716795670
976 8908190622929818989104589780084
977 9272154005774198875405922968919
978 9650794979931743831374519127909
979 10044697780763866841620321572242
980 10454469597967926527741317306889
981 10880741465790793678450077800264
982 11324169187321344140027550069487
983 11785434294149672433399590228443
984 12265245042728880818213137164654
985 12764337448825085694785170647370
986 13283476361492946844128754525234
987 13823456578067544687237573504684
988 14385104001718964205112243209341
989 14969276843173472445937993869111
990 15576866868264865918043499158144
991 16208800693041397301714487949350
992 16866041128217843125892277486572
993 17549588574828729888821659484570
994 18260482473007680454443924886897
995 18999802805889262095289033422561
996 19768671660703807323331272517575
997 20568254849212427725886306433144
998 21399763589709055193036427704847
999 22264456252898815972611610521424
1000 23163640174047588085637447001296