0 0
1 1
2 1
3 2
4 4
5 7
6 9
7 14
8 20
9 28
10 41
11 54
12 74
13 99
14 131
15 174
16 226
17 294
18 380
19 485
20 623
21 785
22 996
23 1249
24 1565
25 1952
26 2425
27 3001
28 3707
29 4553
30 5592
31 6828
32 8334
33 10128
34 12291
35 14866
36 17954
37 21617
38 25991
39 31159
40 37311
41 44554
42 53141
43 63229
44 75137
45 89096
46 105515
47 124711
48 147223
49 173475
50 204170
51 239885
52 281525
53 329866
54 386082
55 451200
56 526741
57 614068
58 715126
59 831725
60 966358
61 1121398
62 1300035
63 1505374
64 1741497
65 2012414
66 2323370
67 2679530
68 3087562
69 3554170
70 4087770
71 4697010
72 5392562
73 6185464
74 7089262
75 8118004
76 9288826
77 10619578
78 12131857
79 13848341
80 15796128
81 18003981
82 20505873
83 23338074
84 26543244
85 30166908
86 34262502
87 38887179
88 44107584
89 49995391
90 56633580
91 64111766
92 72533158
93 82009503
94 92669017
95 104650662
96 118113524
97 133230102
98 150197257
99 169228974
100 190568310
101 214480132
102 241264302
103 271247834
104 304800197
105 342324462
106 384275050
107 431148027
108 483501403
109 541944760
110 607162149
111 679901571
112 761000410
113 851374814
114 952048765
115 1064142442
116 1188906163
117 1327707879
118 1482071832
119 1653666276
120 1844347009
121 2056145430
122 2291318129
123 2552335344
124 2841937471
125 3163124167
126 3519219372
127 3913860820
128 4351074948
129 4835268083
130 5371311396
131 5964535363
132 6620826519
133 7346624969
134 8149035940
135 9035831101
136 10015576487
137 11097639597
138 12292336146
139 13610943994
140 15065871932
141 16670682767
142 18440286566
143 20390975730
144 22540647089
145 24908850352
146 27517044590
147 30388663641
148 33549410776
149 37027346131
150 40853225826
151 45060614714
152 49686278108
153 54770325596
154 60356662065
155 66493170450
156 73232231568
157 80630952116
158 88751765581
159 97662714797
160 107438145133
161 118159053495
162 129913889075
163 142798979758
164 156919458396
165 172389782740
166 189334804259
167 207890401109
168 228204712931
169 250438904501
170 274768595703
171 301384779715
172 330495476397
173 362326835776
174 397125049570
175 435157671777
176 476715830051
177 522115802984
178 571701576269
179 625846722557
180 684957359224
181 749474378746
182 819876874028
183 896684781917
184 980462843306
185 1071823735954
186 1171432652283
187 1280011000789
188 1398341702410
189 1527273554758
190 1667727357611
191 1820701052252
192 1987276806172
193 2168627053402
194 2366022687620
195 2580840156937
196 2814570929147
197 3068829818087
198 3345365920871
199 3646072366876
200 3972998961841
201 4328363588372
202 4714566813287
203 5134205212495
204 5590088238978
205 6085253778164
206 6622987623564
207 7206841619154
208 7840656135467
209 8528581208276
210 9275102478000
211 10085065784597
212 10963707100521
213 11916681127751
214 12950095813146
215 14070545582848
216 15285151127350
217 16601597982738
218 18028182386832
219 19573856026503
220 21248278870148
221 23061871029320
222 25025873610563
223 27152408770776
224 29454549781052
225 31946390530224
226 34643126150148
227 37561133404476
228 40718063442793
229 44132934693039
230 47826239548264
231 51820051633734
232 56138148458969
233 60806135218980
234 65851585742861
235 71304185280142
236 77195892419923
237 83561103674252
238 90436839408286
239 97862933433877
240 105882246444025
241 114540884264328
242 123888442778803
243 133978259036237
244 144867692176779
245 156618412197959
246 169296722049583
247 182973889500889
248 197726516316292
249 213636919442665
250 230793553974247
251 249291450764494
252 269232700835035
253 290726957484585
254 313891990860125
255 338854263787787
256 365749566393690
257 394723676162803
258 425933083900079
259 459545749922273
260 495741934217216
261 534715062346506
262 576672674366569
263 621837415909890
264 670448122440087
265 722760953050503
266 779050628900443
267 839611729683828
268 904760107610676
269 974834369215696
270 1050197489178556
271 1131238503161144
272 1218374349041584
273 1312051799987459
274 1412749564317243
275 1520980491967818
276 1637293968424446
277 1762278432115530
278 1896564102619124
279 2040825851571214
280 2195786310646472
281 2362219144268176
282 2540952588941804
283 2732873182408488
284 2938929792753574
285 3160137865936025
286 3397584010734504
287 3652430834779366
288 3925922160156351
289 4219388527211826
290 4534253125481988
291 4872038055008308
292 5234371068243505
293 5622992690393083
294 6039763880488503
295 6486674125422024
296 6965850142486279
297 7479565076747806
298 8030248383124796
299 8620496273590224
300 9253082934790004
301 9930972390410008
302 10657331230492969
303 11435542075702736
304 12269218017044064
305 13162217892804904
306 14118662662957326
307 15142952736463069
308 16239786533361424
309 17414180130603563
310 18671488296977860
311 20017426759874683
312 21458096034567184
313 23000006652616900
314 24650106147872177
315 26415807630517762
316 28305020337854721
317 30326181986606191
318 32488293348131255
319 34800954866005072
320 37274405773207235
321 39919565523353289
322 42748078032196942
323 45772358539707579
324 49005643631250891
325 52462044224721478
326 56156602108644375
327 60105349835309621
328 64325374604626928
329 68834885941453198
330 73653287857090184
331 78801255297766430
332 84300815631177704
333 90175434975352919
334 96450110186852086
335 103151466316225279
336 110307860419620697
337 117949491540273782
338 126108517827783497
339 134819180617112943
340 144117936521500933
341 154043597373018371
342 164637479159009020
343 175943559803473755
344 188008647045141102
345 200882556280320897
346 214618299735710844
347 229272286863419988
348 244904537447357947
349 261578907342888399
350 279363328475203788
351 298330063054016684
352 318555973779332170
353 340122810039321447
354 363117512038587567
355 387632532909230267
356 413766180923263585
357 441622981918988453
358 471314064257730669
359 502957566495028400
360 536679070299401358
361 572612058886429152
362 610898403739940901
363 651688879984924206
364 695143713446314484
365 741433159871087977
366 790738119636051424
367 843250788548787519
368 899175348381957560
369 958728697897810231
370 1022141228352401997
371 1089657644409039739
372 1161537834834165704
373 1238057794102884447
374 1319510599710777526
375 1406207446544315511
376 1498478743572934775
377 1596675274472613582
378 1701169427957162077
379 1812356499720303825
380 1930656072330755625
381 2056513475316380385
382 2190401332402943003
383 2332821198522492657
384 2484305294243425883
385 2645418340666156937
386 2816759503194714338
387 2998964447712577850
388 3192707518408998063
389 3398704041332952410
390 3617712763841694382
391 3850538434640813059
392 4098034535599240901
393 4361106170734180430
394 4640713124670750882
395 4937873096758522450
396 5253665124386499294
397 5589233202564091795
398 5945790114675706114
399 6324621482471253244
400 6727090051707092458
401 7154640222619077576
402 7608802843304060348
403 8091200276447676223
404 8603551759310870623
405 9147679068820303689
406 9725512513702164166
407 10339097267083008526
408 10990600063733882516
409 11682316277149145429
410 12416677403106846112
411 13196258966879908363
412 14023788883472089555
413 14902156290261938594
414 15834420884438893296
415 16823822787088614520
416 17873792969637908249
417 18987964267278303988
418 20170183018751148404
419 21424521360199397102
420 22755290216522278348
421 24167053021382092191
422 25664640213776860508
423 27253164546167955131
424 28938037257020679069
425 30724985147029227168
426 32620068617342675162
427 34629700713834229562
428 36760667241760350063
429 39020148000164213211
430 41415739207027377499
431 43955477170441175378
432 46647863284150296752
433 49501890409324109912
434 52527070729025078685
435 55733465144550939472
436 59131714309082047170
437 62733071375953214761
438 66549436566874086188
439 70593393646467527741
440 74878248419373802589
441 79418069346343805289
442 84227730407627305387
443 89322956321248801352
444 94720370257785911862
445 100437544171642493768
446 106493051905125917199
447 112906525199079970993
448 119698712782601073380
449 126891542690859220306
450 134508188001447565026
451 142573136155218831507
452 151112262071785425429
453 160152905244418442864
454 169723951046319300270
455 179855916453815963281
456 190581040442505990508
457 201933379284965010805
458 213948907032579564758
459 226665621435673930838
460 240123655613763750955
461 254365395758408659131
462 269435605212785231482
463 285381555241787911301
464 302253162872398143384
465 320103136152810262529
466 338987127249337772800
467 358963893767970462267
468 380095468762923315251
469 402447339861509215498
470 426088638015445036591
471 451092336354883506192
472 477535459707946157634
473 505499305313981190554
474 535069675351378207591
475 566337121865570787653
476 599397204782061154904
477 634350763653540295474
478 671304203896478893414
479 710369798236369005586
480 751666004194727404085
481 795317798414485888254
482 841457028742544504875
483 890222784951641992627
484 941761789114704481667
485 996228806608272900423
486 1053787078862147373456
487 1114608778936110867693
488 1178875491155412357322
489 1246778716000941469936
490 1318520401611930572409
491 1394313503224099768500
492 1474382572040007301577
493 1558964374994612358968
494 1648308547065797982013
495 1742678277747377302974
496 1842351033502766773645
497 1947619317987255285884
498 2058791472042472228752
499 2176192515438864671460
500 2300165032573890836014
501 2431070104308843569389
502 2569288288376643670359
503 2715220650771779588220
504 2869289850801923562423
505 3031941282463924399385
506 3203644275095701421926
507 3384893356243837012287
508 3576209579997629342435
509 3778141924034633464954
510 3991268758957612978990
511 4216199393504075593905
512 4453575699570362760192
513 4704073821001583660891
514 4968405970487519808543
515 5247322318923257634721
516 5541612982012477770139
517 5852110108920650159287
518 6179690078237417599429
519 6525275806548969517981
520 6889839175408842680496
521 7274403582551016854623
522 7680046623715360605813
523 8107902911526722800673
524 8559167038436947395842
525 9035096690828218167686
526 9537015921989433412216
527 10066318591786674231826
528 10624471981511229416264
529 11213020592520829332468
530 11833590138005414005668
531 12487891737366614274686
532 13177726323473595493566
533 13904989273244616132652
534 14671675272839809423179
535 15479883428969764172861
536 16331822638728680937690
537 17229817230616166008785
538 18176312890389791988720
539 19173882885686359746303
540 20225234604408030677207
541 21333216422210561515936
542 22500824915576182067764
543 23731212437345168379490
544 25027695072820049076330
545 26393760995004123995415
546 27833079238878560792130
547 29349508915132667550767
548 30947108885216125327197
549 32630147920161852641014
550 34403115367203637191623
551 36270732348869838273642
552 38237963520941696570945
553 40310029416407729338482
554 42492419404396170235459
555 44790905293905431254254
556 47211555614158774272716
557 49760750604352771225131
558 52445197947744613437811
559 55271949286083398005428
560 58248417552750087974754
561 61382395164159953914640
562 64682073111541079778815
563 68156060996534329414464
564 71813408056837645292129
565 75663625229607059478792
566 79716708303341088392130
567 83983162210638790780494
568 88474026517493680563497
569 93200902166641467502199
570 98175979536031734321704
571 103412067875561422498887
572 108922626189065051890164
573 114721795630858013832763
574 120824433490318114420189
575 127246148840549460642667
576 134003339931722590201715
577 141113233412527290729289
578 148593925468117208197053
579 156464424966080074138124
580 164744698707337581688191
581 173455718882377226130561
582 182619512839053888570153
583 192259215272075127324145
584 202399122950626025007924
585 213064752104881066844970
586 224282898599043619285436
587 236081701023301846346935
588 248490706844582902289212
589 261540941761237206978592
590 275264982414930660184558
591 289697032618823530390244
592 304873003269971692263365
593 320830596120291629849200
594 337609391590061327939656
595 355250940814998774382103
596 373798862128432835901839
597 393298942187879143968642
598 413799241966723633351016
599 435350207840313054187231
600 458004788008139918078970
601 481818554503281873811813
602 506849831053730271734994
603 533159827070675173671630
604 560812778053471740590561
605 589876092712497427459998
606 620420507127054699516290
607 652520246268110985318282
608 686253193233014585670787
609 721701066553224399218900
610 758949605954964231611231
611 798088766967993586426672
612 839212924798220686934451
613 882421087896677413150503
614 927817121679717740360185
615 975509982873750682766860
616 1025613964982128740521727
617 1078248955392073616101932
618 1133540704665973089005539
619 1191621108583625072437485
620 1252628503530788684463824
621 1316707975853810997076473
622 1384011685831419831818497
623 1454699206941550831158778
624 1528937881135160830401155
625 1606903190858347080602707
626 1688779148601181833344998
627 1774758704783869419548314
628 1865044174831194560958486
629 1959847686321520664413993
630 2059391647140518746230349
631 2163909235608475887920217
632 2273644913597828471767754
633 2388854963699923330459817
634 2509808051552022357644722
635 2636785814481953198697280
636 2770083477684408451189479
637 2910010499193681973357037
638 3056891244979222146576633
639 3211065695545969972062075
640 3372890185488471880167910
641 3542738177508585949871070
642 3721001072479530458768975
643 3908089057205571255032468
644 4104431991606002224799589
645 4310480337124859737573512
646 4526706128254161802111203
647 4753603989138055029470060
648 4991692197319207869007958
649 5241513796775803545706118
650 5503637762499714101297710
651 5778660218961545671621824
652 6067205714919470686522250
653 6369928557132695903513513
654 6687514205661425958872637
655 7020680733548734945294458
656 7370180353811410715254871
657 7736801016790873883838191
658 8121368081058497411512878
659 8524746061205115492908544
660 8947840456000316669031214
661 9391599660555028092492823
662 9857016966290384584702287
663 10345132652677350310679996
664 10857036174895921078790035
665 11393868451738982340971431
666 11956824258286427180264786
667 12547154728067474866719433
668 13166169969647236354501985
669 13815241802783429406761316
670 14495806619536357052811426
671 15209368375944195105647078
672 15957501720133610493155065
673 16741855262985430727383149
674 17564154997755628558334430
675 18426207875324188276077926
676 19329905542049488786743441
677 20277228247502741769671046
678 21270248929688741500830223
679 22311137485682856460372783
680 23402165235974867759184158
681 24545709591163059987857667
682 25744258930034105865917223
683 27000417698448774144313919
684 28316911738879804601281182
685 29696593860867250545263977
686 31142449663120032344712001
687 32657603618448890443829494
688 34245325433219699630758099
689 35909036693513319375053547
690 37652317810725732276265956
691 39478915279883764795279362
692 41392749264546835250078198
693 43397921522754910899045087
694 45498723689129670113776436
695 47699645928877994076638813
696 50005385980149826402488916
697 52420858601901514398210084
698 54951205445179572487655212
699 57601805366500773949721851
700 60378285202834437307262781
701 63286531028520994759234315
702 66332699915362685244848826
703 69523232218023512686578270
704 72864864407855300709488518
705 76364642479247365620927020
706 80029935953661614361976784
707 83868452507581809286300868
708 87888253251761840192404993
709 92097768690318456411071748
710 96505815389469652051956565
711 101121613386982248113315650
712 105954804374756083581263177
713 111015470688345059417328088
714 116314155138696474703394309
715 121861881722882887891165639
716 127670177252209229970953950
717 133751093937700931249808398
718 140117232974725423136459017
719 146781769170263797737516441
720 153758476658245825378651929
721 161061755750279420263232886
722 168706660971164571570808950
723 176708930330666212105434195
724 185085015885255685899284847
725 193852115645795690751967537
726 203028206889569922689280210
727 212632080937520007377160952
728 222683379460185958715082887
729 233202632378520576111050397
730 244211297428606637840148065
731 255731801462210795587750163
732 267787583558210252208004142
733 280403140023083798938421579
734 293604071362025211175158718
735 307417131305664142763957028
736 321870277981032544840476886
737 336992727319136388247736864
738 352815008795455876195162689
739 369369023603738573174038728
740 386688105367749856959609478
741 404807083500032764679947463
742 423762349321394064202898812
743 443591925059596644254531374
744 464335535850798392326136511
745 486034684872448178627549908
746 508732731741838012571494730
747 532474974320122275560645510
748 557308734067567536881585812
749 583283445101886712614425138
750 610450747117966813232928411
751 638864582333908277324850742
752 668581296635294172158293953
753 699659745096778177582603026
754 732161402067670709061814952
755 766150476015982013427348849
756 801694029333610746525195810
757 838862103313805680333998729
758 877727848520950204406697422
759 918367660781873076312242148
760 960861323037560688837492730
761 1005292153304074065715153212
762 1051747159001957559477515048
763 1100317197924192700574634440
764 1151097146124113590561867582
765 1204186073016374883483322535
766 1259687423996378245602947964
767 1317709210896221348844169762
768 1378364210608578850152405887
769 1441770172223647976400500580
770 1508050033038752337595618172
771 1577332143815073892696716157
772 1649750503671651576504468425
773 1725445005022909843669555468
774 1804561688982955998791730205
775 1887253011677361440835359603
776 1973678121921532114058927319
777 2064003150743712668099618633
778 2158401513250589785476395723
779 2257054223353982783042080749
780 2360150221898686995736110984
781 2467886718753771791782929746
782 2580469549453004739713853545
783 2698113546994164282461668580
784 2821042929432312014847599946
785 2949491703928193182673510148
786 3083704087940340483364552078
787 3223934948277724946478440780
788 3370450258759473302419972497
789 3523527577258788885862512709
790 3683456542940343177685256081
791 3850539394533563763206243427
792 4025091510519029134739327338
793 4207441972141088040420882878
794 4397934150197476582881291728
795 4596926316595586402985717784
796 4804792281705797260320501155
797 5021922058584382589593051724
798 5248722555182613424660080238
799 5485618295704258207060945709
800 5733052172321422229164108658
801 5991486228508002146139918866
802 6261402475301701046918885115
803 6543303741858946159154508588
804 6837714561722963081009364702
805 7145182096283051683458321079
806 7466277096963605742052948568
807 7801594907743960385763828623
808 8151756509675604191199441708
809 8517409609130970093995461242
810 8899229771588828128021513295
811 9297921602834530855411895727
812 9714219979529959430809049157
813 10148891331187244861756091884
814 10602734975663190860566746112
815 11076584510377033987739660446
816 11571309261543786945284778316
817 12087815793808125243625787036
818 12627049482760689488629625673
819 13189996152918958799012758094
820 13777683783859651381933668798
821 14391184287298069006644601659
822 15031615358023124214166277929
823 15700142401714084012834547060
824 16397980542787590662187578766
825 17126396715550357972363044122
826 17886711842065410317225446365
827 18680303100276877028974317745
828 19508606286081560888860694642
829 20373118273183777652940040963
830 21275399574724764960227013988
831 22217077010838260133014825350
832 23199846486451168835243358464
833 24225475883821530976185384179
834 25295808074486832284644556735
835 26412764055483013558592204135
836 27578346214889968255333955762
837 28794641731961759162938507777
838 30063826117310981801969447253
839 31388166898835483871120836950
840 32770027459303857964225806550
841 34211871031752547675337956097
842 35716264859093977072692071014
843 37285884524590579122173193418
844 38923518460115987168210656600
845 40632072639400673101319145527
846 42414575463747093673975608993
847 44274182847997609266479716933
848 46214183514849299905507302039
849 48238004505931946187742130336
850 50349216918401211462427203506
851 52551541876147038281682380230
852 54848856745079916896859055245
853 57245201602333535480491445724
854 59744785969613963744570970136
855 62351995821331449202886608976
856 65071400878573830743153237437
857 67907762200418949060243544986
858 70866040084540106261659114148
859 73951402289532005110580491615
860 77169232591877673727414591106
861 80525139690988017399709334295
862 84024966476277978337215755275
863 87674799670795145763137088895
864 91480979866491344719516980543
865 95450111966823517267620455228
866 99589076052990564205584185279
867 103905038690755970036214423074
868 108405464695475635366171424253
869 113098129373644576830802009624
870 117991131259998858131034504761
871 123092905369958431717765641739
872 128412236987976528790876608090
873 133958276013169938570088777230
874 139740551884446203359274974434
875 145768989108216485921186766398
876 152053923412691096008072395059
877 158606118553696416247668303286
878 165436783797931930727961509327
879 172557592110602217404202009057
880 179980699075416048304200408173
881 187718762576041098367576116877
882 195784963269243382281903232136
883 204193025881123334189546704555
884 212957241359090876888223896893
885 222092489913497779478144151406
886 231614264984172821421414568177
887 241538698168481623102616119858
888 251882585148964517314251788414
889 262663412660090354676309475208
890 273899386535208028069361348032
891 285609460876378578361426284779
892 297813368391435713601204330609
893 310531651944349232222814801277
894 323785697366761252827948361080
895 337597767580427103850400115782
896 351991038082228659108215189169
897 366989633845435600011384992470
898 382618667692977385082200851260
899 398904280200653394042935964699
900 415873681190459052974954156227
901 433555192876539529244643909365
902 451978294728708523337408052015
903 471173670120985586460798986493
904 491173254835220444486353640373
905 512010287492584843164084452442
906 533719361988531134305466456789
907 556336482009740066015283941108
908 579899117714618240185083358349
909 604446264662056372057500352308
910 630018505076433609458674497286
911 656658071540248716565176724420
912 684408913209287273298100449023
913 713316764648893231829028501715
914 743429217393715210707296864653
915 774795794337240926556298219571
916 807468027061529835093677947167
917 841499536221802611870740634237
918 876946115104959927882182670863
919 913865816485680420928784235517
920 952319042908502959307180214516
921 992368640529229734689605367165
922 1034079996654109329731281606004
923 1077521141120571338647603307440
924 1122762851668802142276618246246
925 1169878763459173892882353967590
926 1218945482896482308476673160255
927 1270042705928112561253865914159
928 1323253340989653978266580849547
929 1378663636778122741543892108552
930 1436363315039845893778974520399
931 1496445708567209278859447505036
932 1559007904605896255607134417251
933 1624150893881942972951161836649
934 1691979725465930500050744143720
935 1762603667699924356715858331223
936 1836136375421380005192589057978
937 1912696063727159210404553371509
938 1992405688530070146364978530716
939 2075393134169954705817016972062
940 2161791408351324308595795302774
941 2251738844689892049625287572274
942 2345379313161090370564947613851
943 2442862438754801541625851861503
944 2544343828652090722766808996216
945 2649985308251720766182028473620
946 2759955166386673471244273195893
947 2874428410083806865673973489759
948 2993587029233173236858601444340
949 3117620271547411922591282931392
950 3246724928206047101474096741638
951 3381105630594468607463006347407
952 3520975158562887892987376322491
953 3666554760646647123243998026970
954 3818074486705953838497583338028
955 3975773533460423029962448138973
956 4139900603411771882844804684902
957 4310714277666637209476024768928
958 4488483403190813118064752485059
959 4673487495046245198998395890580
960 4866017154182911349357069926829
961 5066374501379277958966383142563
962 5274873627947390092456109591148
963 5491841063841846494823906834185
964 5717616263835974093525913151606
965 5952552112453464573020933675369
966 6197015448369619935905839281494
967 6451387609023188703927858698967
968 6716064996207615130846579541328
969 6991459663439386163176036813740
970 7277999925931103879836235030138
971 7576130994027952284218831306310
972 7886315630998429224648232354299
973 8209034836103596411340516385162
974 8544788553903729453903971027685
975 8894096410797147280996542924931
976 9257498479823236809235896228562
977 9635556074800288396560250944112
978 10028852574908795411487968465897
979 10437994280872373849209073983990
980 10863611303931504957993179735299
981 11306358488849924779632436504381
982 11766916372239763953930244558926
983 12245992177539511599823721209567
984 12744320848028628456093448034980
985 13262666119314202542899839092754
986 13801821632778520922635768345692
987 14362612091531863058527303430579
988 14945894460472306332408250539351
989 15552559212113915711071512679458
990 16183531619906475287804814905778
991 16839773100833956869388694799100
992 17522282609145324698257189173711
993 18232098083140097708308595000464
994 18970297947002453454948381464511
995 19738002669751617832213644110490
996 20536376383452971690710267013868
997 21366628562913781574322619203022
998 22230015769169865066411467347097
999 23127843459154899454283110751678
1000 24061467864032622462908620634448