1 0
2 1
3 1
4 3
5 3
6 7
7 8
8 14
9 18
10 28
11 35
12 53
13 67
14 94
15 121
16 165
17 209
18 280
19 353
20 462
21 582
22 749
23 935
24 1192
25 1480
26 1862
27 2302
28 2871
29 3526
30 4366
31 5335
32 6555
33 7976
34 9737
35 11789
36 14317
37 17259
38 20845
39 25032
40 30093
41 35992
42 43087
43 51347
44 61216
45 72710
46 86362
47 102235
48 121021
49 142824
50 168509
51 198297
52 233247
53 273707
54 321034
55 375729
56 439492
57 513088
58 598620
59 697173
60 811429
61 942854
62 1094813
63 1269368
64 1470702
65 1701596
66 1967351
67 2271643
68 2621125
69 3020722
70 3478731
71 4001627
72 4599877
73 5281878
74 6060736
75 6947437
76 7958319
77 9107562
78 10415678
79 11900824
80 13588625
81 15502399
82 17674041
83 20133278
84 22919963
85 26071752
86 29638251
87 33667237
88 38220293
89 43357677
90 49155987
91 55690911
92 63057437
93 71350634
94 80688021
95 91188534
96 102997678
97 116263724
98 131166397
99 147890458
100 166657458
101 187696873
102 211281808
103 237696535
104 267277021
105 300375082
106 337403283
107 378795934
108 425059448
109 476728734
110 534424289
111 598804250
112 670627684
113 750702591
114 839956879
115 939380654
116 1050106420
117 1173346009
118 1310479621
119 1462987770
120 1632551069
121 1820975190
122 2030303583
123 2262735982
124 2520753648
125 2807032012
126 3124581089
127 3476649990
128 3866885330
129 4299228340
130 4778091296
131 5308248119
132 5895032266
133 6544218329
134 7262245314
135 8056090472
136 8933518344
137 9902948201
138 10973733767
139 12156021655
140 13461067062
141 14901085096
142 16489603883
143 18241311069
144 20172450881
145 22300663419
146 24645433220
147 27227924459
148 30071483794
149 33201475087
150 36645846044
151 40434960743
152 44602240518
153 49183999368
154 54220164463
155 59754120435
156 65833522749
157 72510150736
158 79840829049
159 87887297644
160 96717250505
161 106404232217
162 117028813344
163 128678516565
164 141449150335
165 155444777931
166 170779225056
167 187576107453
168 205970540387
169 226109233100
170 248152432212
171 272274104483
172 298664139331
173 327528645040
174 359092451670
175 393599538370
176 431315883385
177 472530056735
178 517556458190
179 566736115304
180 620440370091
181 679071915239
182 743068999119
183 812906754624
184 889101986523
185 972214856301
186 1062854342478
187 1161680338965
188 1269409891517
189 1386819795157
190 1514753707534
191 1654125344941
192 1805926607257
193 1971231469093
194 2151205270717
195 2347109438355
196 2560312096652
197 2792293773362
198 3044659535271
199 3319145834862
200 3617634400129
201 3942160431211
202 4294928484193
203 4678322258451
204 5094922775730
205 5547520010480
206 6039133709590
207 6573027186843
208 7152731149899
209 7782060029395
210 8465139264943
211 9206424566275
212 10010733174240
213 10883266546661
214 11829646152503
215 12855940150093
216 13968704389048
217 15175013699157
218 16482508872197
219 17899433312923
220 19434686844885
221 21097868587587
222 22899338594607
223 24850267909480
224 26962709187343
225 29249655069795
226 31725119062468
227 34404203537778
228 37303192370469
229 40439630022590
230 43832427653128
231 47501955006477
232 51470161903565
233 55760684906383
234 60398986425631
235 65412478366326
236 70830681401153
237 76685368182925
238 83010745634049
239 89843620684437
240 97223608892428
241 105193326028817
242 113798626809630
243 123088826193331
244 133116972464944
245 143940102664338
246 155619554929082
247 168221263026380
248 181816113542719
249 196480285276569
250 212295657560803
251 229350201084539
252 247738444589046
253 267561924525559
254 288929718364650
255 311958961626578
256 336775457086207
257 363514268901358
258 392320418370037
259 423349566136504
260 456768806613083
261 492757450870050
262 531507933384721
263 573226709959060
264 618135292429968
265 666471277818577
266 718489528757520
267 774463352417268
268 834685846688095
269 899471249958133
270 969156475923628
271 1044102658032879
272 1124696898872451
273 1211354036458980
274 1304518637495725
275 1404667016365179
276 1512309505617073
277 1627992762522954
278 1752302354608093
279 1885865393467634
280 2029353478027321
281 2183485700629724
282 2349031996543861
283 2526816573165515
284 2717721720710113
285 2922691722311221
286 3142737187902493
287 3378939510652684
288 3632455794391749
289 3904523930273304
290 4196468197329688
291 4509705043190496
292 4845749447556739
293 5206221501805695
294 5592853637111942
295 6007498109962345
296 6452135209881078
297 6928881772078128
298 7440000494421055
299 7987909614206448
300 8575193481043703
301 9204613552258163
302 9879120387275574
303 10601866136414743
304 11376218143401226
305 12205773124835403
306 13094372591702816
307 14046118941884725
308 15065392938512031
309 16156871966694226
310 17325549836623783
311 18576757487800999
312 19916185419218445
313 21349907160144184
314 22884404668094654
315 24526594926136649
316 26283858692149042
317 28164070628219274
318 30175631833492478
319 32327503962133583
320 34629246026496163
321 37091053018045286
322 39723797528331364
323 42539073451918181
324 45549243041647109
325 48767486344782993
326 52207854386082034
327 55885325070218538
328 59815863272155250
329 64016484030297361
330 68505320421034063
331 73301694969108111
332 78426196291900615
333 83900759768896486
334 89748754062670195
335 95995072218177878
336 102666229304471572
337 109790465258431589
338 117397855044291190
339 125520424718729208
340 134192275676171634
341 143449715593391016
342 153331398521099335
343 163878472568552526
344 175134737816902801
345 187146812832080019
346 199964312615355448
347 213640036287051894
348 228230167559620687
349 243794486218586098
350 260396593904646228
351 278104152337187068
352 296989137528080740
353 317128108049044851
354 338602491177190787
355 361498884904716084
356 385909379937326287
357 411931899590318094
358 439670562030797540
359 469236062701308919
360 500746081723344683
361 534325714044191017
362 570107927506561243
363 608234046535467878
364 648854267033810396
365 692128200118752049
366 738225450736294211
367 787326228728968505
368 839621998879838653
369 895316167457330728
370 954624812310290942
371 1017777453998836714
372 1085017875580800615
373 1156604988510776670
374 1232813752893462946
375 1313936149532387027
376 1400282212690405371
377 1492181121005700057
378 1589982356212154100
379 1694056927128480088
380 1804798669364297819
381 1922625618249502479
382 2047981466303637926
383 2181337102822366492
384 2323192247842072659
385 2474077178159584610
386 2634554558699433390
387 2805221377039371562
388 2986710995508905377
389 3179695318848716127
390 3384887093067779660
391 3603042333708263581
392 3834962900490905468
393 4081499216824944713
394 4343553152611055375
395 4622081069159408147
396 4918097046238545838
397 5232676290482934379
398 5566958746911454869
399 5922152913267546724
400 6299539880828141531
401 6700477601968005373
402 7126405410195292957
403 7578848793620276102
404 8059424449838192518
405 8569845623976213475
406 9111927760360096217
407 9687594470471967488
408 10298883850359536208
409 10947955151233445178
410 11637095839376945062
411 12368729050332024060
412 13145421476727745720
413 13969891696131710166
414 14845018981837139996
415 15773852604588595084
416 16759621672048087451
417 17805745515857395455
418 18915844677356230998
419 20093752503931247381
420 21343527411718686557
421 22669465829045013076
422 24076115881445007953
423 25568291835376045328
424 27151089367074545201
425 28829901676779870009
426 30610436520916888444
427 32498734185975624559
428 34501186483425794953
429 36624556793372160952
430 38876001243686600222
431 41263091056806965077
432 43793836159053385267
433 46476710089702060825
434 49320676313580194554
435 52335215980102954667
436 55530357242296158075
437 58916706185119861063
438 62505479487370459224
439 66308538873653384787
440 70338427492498370226
441 74608408285157304699
442 79132504494105353895
443 83925542384813819514
444 89003196344034096036
445 94382036438266576627
446 100079578611282133808
447 106114337615672000754
448 112505882874458993908
449 119274897380389912160
450 126443239847798443451
451 134034010238777494780
452 142071618899280911771
453 150581859442649390205
454 159591985638957814332
455 169130792465264604162
456 179228701600189173439
457 189917851537496308126
458 201232192629634792699
459 213207587257737499049
460 225881915469276184187
461 239295186304193405479
462 253489655183948002655
463 268509947611347335969
464 284403189592159982666
465 301219145056461148539
466 319010360730887988485
467 337832318773205154749
468 357743597664529721794
469 378806041707770536903
470 401084939676208726970
471 424649213002028084135
472 449571614102123601628
473 475928935276801996991
474 503802228837408924575
475 533277038949309346424
476 564443645910816677269
477 597397323410842249934
478 632238609556835376459
479 669073592278263350419
480 708014209975228019002
481 749178568086692814905
482 792691272533719210616
483 838683780788858478533
484 887294771621421985098
485 938670534354691475511
486 992965378788484208778
487 1050342066717117165850
488 1110972266310198685627
489 1175037030390275606107
490 1242727300000092649507
491 1314244434408531680746
492 1389800769085750100091
493 1469620202923783173586
494 1553938816384583896333
495 1643005521992362070908
496 1737082749018661718925
497 1836447163932431226451
498 1941390428646482341501
499 2052219998304250928223
500 2169259960839360662178
501 2292851920241476366471
502 2423355925981951265342
503 2561151450742089964395
504 2706638419140388191348
505 2860238289832624195472
506 3022395193948054295683
507 3193577132490545035011
508 3374277235961137770232
509 3565015089112178955920
510 3766338124411688138118
511 3978823087438339249586
512 4203077578139706052694
513 4439741671516225364349
514 4689489622052373845574
515 4953031655834643651819
516 5231115855104926211226
517 5524530139604518514080
518 5834104349926516827885
519 6160712437689763190582
520 6505274768267351393950
521 6868760541387372422139
522 7252190335904714540960
523 7656638784617231512142
524 8083237386046427557099
525 8533177459667771808864
526 9007713252192979936490
527 9508165202062925192441
528 10035923370502454929882
529 10592451047037089806750
530 11179288538645079029168
531 11798057151260518994996
532 12450463373703481889604
533 13138303273650351437549
534 13863467116710805395991
535 14627944219211820644115
536 15433828046842192267007
537 16283321570843560006164
538 17178742895094268385958
539 18122531166965757701999
540 19117252786606593961844
541 20165607928846060975703
542 21270437393808342192631
543 22434729801871461130290
544 23661629150637175324686
545 24954442751130916550621
546 26316649562625712396533
547 27751908945050497647806
548 29264069850271716142852
549 30857180473121417178640
550 32535498385538816757568
551 34303501176799393019950
552 36165897625477109887986
553 38127639428420768301644
554 40193933514888423736069
555 42370254973653637977924
556 44662360623966363323300
557 47076303260962551887345
558 49618446609407489538859
559 52295481019418407381903
560 55114439941341960781518
561 58082717216780607256538
562 61208085226549650588734
563 64498713936232876140778
564 67963190884070136963503
565 71610542155874980365675
566 75450254396045381040877
567 79492297903785942023389
568 83747150868347981774926
569 88225824797253337062772
570 92939891196504231632330
571 97901509562060029028855
572 103123456747274377253583
573 108619157771400253079857
574 114402718140089161911949
575 120488957749378779527129
576 126893446450920394448388
577 133632541356939935295501
578 140723425970156962947170
579 148184151224825247311880
580 156033678532300679073232
581 164291924925703368270609
582 172979810406035518313497
583 182119307593527163472379
584 191733493796373984000221
585 201846605610721583285627
586 212484096174788531123341
587 223672695202024000477984
588 235440471927931880562006
589 247816901107547111324778
590 260832932211041223438312
591 274521061967678879918161
592 288915410419655345452759
593 304051800650525603660679
594 319967842365127636563683
595 336703019501568552406944
596 354298782068990454261816
597 372798642409038669336061
598 392248276093138317686054
599 412695627672490387986378
600 434191021513002254183505
601 456787277952837864365606
602 480539835036789856684757
603 505506876087883194208554
604 531749463394450744234976
605 559331678297944950620376
606 588320767986003316557540
607 618787299303212397233851
608 650805319912809896381474
609 684452527151489805653239
610 719810444941940232204675
611 756964609137771960952739
612 796004761699769557567415
613 837025054113642807258555
614 880124260485690646774086
615 925406000765378603397714
616 972978974572189976431799
617 1022957206118180390042916
618 1075460300748327490903179
619 1130613713636467987379381
620 1188549031207773042961257
621 1249404265876208981282243
622 1313324164721295801976082
623 1380460532747947955219977
624 1450972571411981860998379
625 1525027233115519768740013
626 1602799592418501852375469
627 1684473234736552050539442
628 1770240663340876400883577
629 1860303725502530700809511
630 1954874058672569900696534
631 2054173557619131782643712
632 2158434863495742277426290
633 2267901875847833157389429
634 2382830288622100564945995
635 2503488151279507192043029
636 2630156456175144377487228
637 2763129753408151454743554
638 2902716794412484186476208
639 3049241205603478144812461
640 3203042193468368110662164
641 3364475282537651965907351
642 3533913087753500416347860
643 3711746122805151272880758
644 3898383646087155938837272
645 4094254545995569143109598
646 4299808267370280294261651
647 4515515780956914163263346
648 4741870597862624425097388
649 4979389831051905488060305
650 5228615306037895298890610
651 5490114723003633701103619
652 5764482872706258795544153
653 6052342908603979461732208
654 6354347677774130880153423
655 6671181113286073382245615
656 7003559690831962060191994
657 7352233952523265181757511
658 7717990100911894474619164
659 8101651666409929787116203
660 8504081251445621047705877
661 8926182354819687742023442
662 9368901279903435346462508
663 9833229130458796383530057
664 10320203898052877018713651
665 10830912645191555071276393
666 11366493788505397439756915
667 11928139486487731708023727
668 12517098136511062022754606
669 13134676986030520881032902
670 13782244863128538527516848
671 14461235031754799662253203
672 15173148177281810627514375
673 15919555528215253698272842
674 16702102120187090085247864
675 17522510208598909460790936
676 18382582836596257960497888
677 19284207565316764664923543
678 20229360373694649647460270
679 21220109735390868757637258
680 22258620880786699625662103
681 23347160252292038715229610
682 24488100161619462712972919
683 25683923658017769343482310
684 26937229616892384855645519
685 28250738058614495496190247
686 29627295707791201560636132
687 31069881803678109147035896
688 32581614172926108363822145
689 34165755576300935550684207
690 35825720341567729444907035
691 37565081295220724652353246
692 39387577006338790549194037
693 41297119356380183281536140
694 43297801449381378411159631
695 45393905877606194686216375
696 47589913358398172032465796
697 49890511758623490637597988
698 52300605523858406072219144
699 54825325530167146371409341
700 57470039377147916381071808
701 60240362141679341561990326
702 63142167612701895868809068
703 66181600028191763522334815
704 69365086336463275466407296
705 72699349004833157372941134
706 76191419399741460773424550
707 79848651763401820574515013
708 83678737813205267044307521
709 87689721991167304734855756
710 91890017391957100866520198
711 96288422399208458451720143
712 100894138061167154500028104
713 105716786237993691853516775
714 110766428554510110225407468
715 116053586193556595527179763
716 121589260566717579435399757
717 127384954900676491153402318
718 133452696779187101393946999
719 139805061682281824044740417
720 146455197566212285553278424
721 153416850529394325148630407
722 160704391611662988384996667
723 168332844776076796839137259
724 176317916124715740777062369
725 184676024402021519770727447
726 193424332841619900208712138
727 202580782414854119521603583
728 212164126541851406102279657
729 222193967328434580491824773
730 232690793395002547554849509
731 243676019366211407809627173
732 255172027093336775726477870
733 267202208684142458384985098
734 279791011418386352733108913
735 292963984630295815325439281
736 306747828642928777593048051
737 321170445842816978011062538
738 336260993987173258508973229
739 352049941839727370294264775
740 368569127235467031789568691
741 385851817678671549384539637
742 403932773583191570088842100
743 422848314268394983863891444
744 442636386829148695483950264
745 463336638003058435955049837
746 484990489163553842702497879
747 507641214572677109244020624
748 531334023033248458074549401
749 556116143085806710880707941
750 582036911902025450022986242
751 609147868032522485409720852
752 637502848173810271728465013
753 667158088125885753214240344
754 698172328119359513965353087
755 730606922698353391798163795
756 764525955353415926428202529
757 799996358106661272259356088
758 837088036260027450830350381
759 875873998526185584492396790
760 916430492771047435087847240
761 958837147606190697550208953
762 1003177120079722546495508021
763 1049537249724271941268612146
764 1098008219231852430937937728
765 1148684722036371657327804834
766 1201665637096535281044414748
767 1257054211183863988989488719
768 1314958248993509868182687605
769 1375490311408543762362706604
770 1438767922262430932587024430
771 1504913783958496361972594150
772 1574056002320393465472562176
773 1646328321062863847788346574
774 1721870366288550719157066920
775 1800827901433190933249694760
776 1883353093099351728947170364
777 1969604788236835723006098779
778 2059748803147196963613078981
779 2153958224809278749534506044
780 2252413725043602382427834262
781 2355303888054539030209522478
782 2462825551911845387013085351
783 2575184164556016743882310676
784 2692594154936431044659953848
785 2815279319916046083526136081
786 2943473227602956225773894208
787 3077419637795976800116155487
788 3217372940260157932690441118
789 3363598611577234811964489600
790 3516373691347122814382755413
791 3675987278548098618265396541
792 3842741048896970460108804196
793 4016949794084699733554355890
794 4198941983799367003000045514
795 4389060351485375790592388629
796 4587662504827212180796250244
797 4795121561986152009173350662
798 5011826814660968901898791594
799 5238184419087094449683056121
800 5474618116134842582098104421
801 5721569981714303520550929587
802 5979501208744456215255733436
803 6248892921994929523355476691
804 6530247027162874770203085165
805 6824087095602497922200402714
806 7130959286183251401478608549
807 7451433305812316889375527319
808 7786103410220238603473189569
809 8135589446673112381173597168
810 8500537940343125728088567206
811 8881623226139102613839769171
812 9279548627872674340177542666
813 9695047686711299209872393573
814 10128885440949348087056046246
815 10581859759210281390720891449
816 11054802729279449014460621651
817 11548582104855561373262582713
818 12064102812602420560144619372
819 12602308521978266605381524378
820 13164183280421234154046574415
821 13750753216573014203617621174
822 14363088314332164827810982385
823 15002304260640577783757584376
824 15669564370024823780399376479
825 16366081589035306064153784063
826 17093120583853944050546511838
827 17851999914472193622734538566
828 18644094298979344587164555123
829 19470836971642790816933280447
830 20333722138611270267787308693
831 21234307535225351920365671504
832 22174217089080807193288519322
833 23155143693156230176294519419
834 24178852093490651529023335161
835 25247181896076059390120343892
836 26362050697818177886122970989
837 27525457346612537072616267886
838 28739485335786480292033066410
839 30006306338367110347928972900
840 31328183886855168833929312747
841 32707477204411118869897255491
842 34146645193597375626433232260
843 35648250589065171690874115870
844 37214964280831301861568046216
845 38849569815054253167077808549
846 40554968079496578732051005600
847 42334182181145919290424963464
848 44190362523766654298866966464
849 46126792093462681601502362325
850 48146891960655385344712396363
851 50254227007214160381374307151
852 52452511887826299041675614841
853 54745617235053107958688786505
854 57137576117896479042612426498
855 59632590764089068433322226157
856 62235039556728713211367048003
857 64949484316297792659007389966
858 67780677879548208228064934872
859 70733571987186337324494959363
860 73813325492767330901581201349
861 77025312905698057324655435961
862 80375133281760811790038809311
863 83868619475098947702088961079
864 87511847766159173083633594580
865 91311147880656471259081183803
866 95273113415225159321889021258
867 99404612686036305671029221557
868 103712800017306694884474273655
869 108205127487290296531990988231
870 112889357150039285564560121626
871 117773573751940335684078901829
872 122866197962783120070614361234
873 128176000141893674859730627632
874 133712114660675921896428049149
875 139484054803741876953979389779
876 145501728271685776909133265850
877 151775453309460902929398871655
878 158315975485261645235498896834
879 165134485145788387710124724840
880 172242635574790999469302295960
881 179652561882838815704679278279
882 187376900657363431649068983501
883 195428810403155792789477623197
884 203821992804683975621137865504
885 212570714842822738882382197515
886 221689831799864021112830840153
887 231194811187998730289169872048
888 241101757637838681376415974253
889 251427438784972682733975428853
890 262189312194037479255001470751
891 273405553361321444626812772515
892 285095084838522196512724549833
893 297277606521937213179278058983
894 309973627153095403396068016044
895 323204497078625550212663716202
896 336992442319021719855149545985
897 351360599997893816621248188471
898 366333055185301377833267868498
899 381934879210847736854394670370
900 398192169504378578480999475383
901 415132091024370536960435509229
902 432782919336431462055995205451
903 451174085406750730311239505198
904 470336222177856047719239769292
905 490301212996638553968573665161
906 511102241967322204577391254902
907 532773846304861893863750210716
908 555351970767180110368106999845
909 578874024247679136749597915703
910 603378938612618504483967160829
911 628907229871210162003240618557
912 655501061769681316978066524275
913 683204311904071255202267633937
914 712062640450189497151134950231
915 742123561612952020353840167123
916 773436517901257060694352757882
917 806052957338645298280625737365
918 840026413724239437301271648392
919 875412590062857885061221885692
920 912269445287776186481552083692
921 950657284404350142251485912006
922 990638852187647323466122437152
923 1032279430572340537718196075289
924 1075646939878430394419788658022
925 1120812044021865480087128476653
926 1167848259864852058549633569910
927 1216832070866571147143280667986
928 1267843045201185217944293952042
929 1320963958516399592317654511107
930 1376280921512482511762138168263
931 1433883512528522305231135513132
932 1493864915329849541439222031693
933 1556322062297955449085430686850
934 1621355783231936646678229596083
935 1689070959978468711591528488942
936 1759576687115600803393862354209
937 1832986438924248277919288400114
938 1909418242890185590451111476037
939 1988994859988585106640519571863
940 2071843972012756571233842755050
941 2158098376218693732419550028130
942 2247896187567379203305534010219
943 2341381048857512364355134325359
944 2438702349052460683291778281559
945 2540015450116768065131167089213
946 2645481922689540080898379600426
947 2755269790934440498646860242052
948 2869553786918934555358432376214
949 2988515614888776748017281246994
950 3112344225817625599871657591149
951 3241236102626049326404098845180
952 3375395556479128667276610514902
953 3515035034587340412618060800345
954 3660375439951484651743580588651
955 3811646463509074181875639704923
956 3969086929156906561095275804501
957 4132945152142461305856649947356
958 4303479311335381042189650363494
959 4480957835909579053788993695807
960 4665659806986544744989363993263
961 4857875374811165830812180595421
962 5057906192052933695519408433828
963 5266065863847718901650224373414
964 5482680415218483619658127157706
965 5708088776537309215863911970694
966 5942643287716051173714079386991
967 6186710221838762282943566747292
968 6440670328975844104557526369694
969 6704919400947668452664043052391
970 6979868857834255481711537913681
971 7265946357057475350158897157935
972 7563596425893262044438937317500
973 7873281118303463375375530795926
974 8195480697010311633527338674418
975 8530694341771057759592651689748
976 8879440884846185228868569606579
977 9242259574691781388713244726760
978 9619710868945216980973391803757
979 10012377257813242747759472914592
980 10420864119013085143818637924349
981 10845800605460085612931770540798
982 11287840566940016315768642526980
983 11747663507050394751422915278414
984 12225975576743054377295376433372
985 12723510605849884171314047924464
986 13241031174025178795038607036876
987 13779329722591419793087462912439
988 14339229708830696962335348425134
989 14921586804321356143080374092773
990 15527290138978993715117536034577
991 16157263592522589049573860353932
992 16812467135150551697419219807929
993 17493898219277741971044753536240
994 18202593224253289087224350079544
995 18939628956050263983426390870851
996 19706124203992161816978279393313
997 20503241356657698092288073683903
998 21332188079184830688771039178860
999 22194219054277176456068739536509
1000 23090637789301315326371081106186