0 0
1 1
2 1
3 2
4 2
5 4
6 5
7 8
8 10
9 16
10 20
11 29
12 37
13 52
14 66
15 90
16 113
17 151
18 190
19 248
20 310
21 400
22 497
23 632
24 782
25 985
26 1212
27 1512
28 1851
29 2291
30 2793
31 3431
32 4163
33 5084
34 6142
35 7456
36 8972
37 10836
38 12989
39 15613
40 18646
41 22316
42 26561
43 31659
44 37556
45 44601
46 52743
47 62416
48 73593
49 86809
50 102064
51 120025
52 140736
53 165028
54 193011
55 225710
56 263333
57 307161
58 357521
59 416006
60 483129
61 560864
62 649960
63 752877
64 870677
65 1006426
66 1161604
67 1340012
68 1543687
69 1777365
70 2043780
71 2348821
72 2696156
73 3093095
74 3544485
75 4059416
76 4644241
77 5310255
78 6065739
79 6924691
80 7897846
81 9002580
82 10252687
83 11669704
84 13271328
85 15084211
86 17130918
87 19444436
88 22053415
89 24998640
90 28316370
91 32056941
92 36266093
93 41005947
94 46333953
95 52326672
96 59056128
97 66616548
98 75097925
99 84616150
100 95283359
101 107241923
102 120631254
103 135625995
104 152399071
105 171164557
106 192136373
107 215576593
108 241749411
109 270975242
110 303579637
111 339953965
112 380498578
113 425690950
114 476022556
115 532075157
116 594451027
117 663858302
118 741033636
119 826837956
120 922170954
121 1028078054
122 1145656219
123 1276173587
124 1420965540
125 1581568632
126 1759606135
127 1956937635
128 2175533518
129 2417642016
130 2685651311
131 2982276475
132 3310408366
133 3673322195
134 4074512536
135 4517926253
136 5007782198
137 5548831584
138 6146161389
139 6805484958
140 7532928545
141 8335355650
142 9220135073
143 10195503546
144 11270314440
145 12454442414
146 13758512241
147 15194350744
148 16774694260
149 18513693839
150 20426600638
151 22530330140
152 24843125486
153 27385187785
154 30178316087
155 33246612592
156 36616099292
157 40315506042
158 44375864634
159 48831390225
160 53719052545
161 59079562675
162 64956922535
163 71399529150
164 78459704991
165 86194934299
166 94667375548
167 103945247454
168 114102327226
169 125219503502
170 137384265759
171 150692445800
172 165247702967
173 181163478912
174 198562486204
175 217578902413
176 238357872709
177 261057974047
178 285850741772
179 312923440362
180 342478628789
181 374737275534
182 409938381443
183 448342484721
184 490231360871
185 535911970005
186 585716259725
187 640005611405
188 699170778533
189 763636898176
190 833863599420
191 910350657428
192 993638316401
193 1084313669342
194 1183011249309
195 1290420233355
196 1407285361444
197 1534415077278
198 1672682847961
199 1823036366105
200 1986499358230
201 2164181992422
202 2357283273065
203 2567102821165
204 2795043974057
205 3042627122079
206 3311493653526
207 3603421062158
208 3920327895383
209 4264290877936
210 4637551051529
211 5042533188856
212 5481853346425
213 5958340884921
214 6475047685202
215 7035273138840
216 7642575323118
217 8300799367402
218 9014090932118
219 9786928420126
220 10624139151255
221 11530935954694
222 12512936497419
223 13576204860949
224 14727274556605
225 15973195779023
226 17321562713039
227 18780567257515
228 20359031328722
229 22066467946444
230 23913119348587
231 25910026464628
232 28069073768483
233 30403068308605
234 32925792372436
235 35652093394379
236 38597945669677
237 41780552651027
238 45218419119376
239 48931467594861
240 52941122589176
241 57270443078809
242 61944220705169
243 66989130538333
244 72433845348672
245 78309207198319
246 84648360225397
247 91486945934852
248 98863257294121
249 106818460997215
250 115396776053836
251 124645726756016
252 134616349409697
253 145363480221008
254 156945994342394
255 169427133485129
256 182874782022904
257 197361839793595
258 212966540683460
259 229772876802972
260 247870965742260
261 267357533153993
262 288336335710235
263 310918710084228
264 335224059632175
265 361380478813866
266 389525312739187
267 419805867301272
268 452380051961602
269 487417187250223
270 525098742603510
271 565619254418607
272 609187172382474
273 656025903041194
274 706374779857052
275 760490249255397
276 818646981735067
277 881139219569289
278 948282048644352
279 1020412929553802
280 1097893152456114
281 1181109576176798
282 1270476291387940
283 1366436595540219
284 1469464893062171
285 1580068937617744
286 1698792001804765
287 1826215422374719
288 1962961076249695
289 2109694268949485
290 2267126558628187
291 2436019033230519
292 2617185529704191
293 2811496351331932
294 3019881935500995
295 3243337069283114
296 3482925066150782
297 3739782545412617
298 4015124186097030
299 4310248144331735
300 4626541461530177
301 4965486203273301
302 5328665608955017
303 5717771046486883
304 6134609001773796
305 6581108955643450
306 7059331324242740
307 7571476378118214
308 8119893258923029
309 8707090075877362
310 9335744140174361
311 10008713391247362
312 10729048008373348
313 11500003338401991
314 12325053064390141
315 13207903828187452
316 14152510158701948
317 15163091007121797
318 16244146663115651
319 17400477447769442
320 18637202874879430
321 19959782777454351
322 21374039003548443
323 22886179286708273
324 24502821802193240
325 26231022130362475
326 28078301039949787
327 30052674936877675
328 32162687286937682
329 34417442991249831
330 36826643912100015
331 39400627670790814
332 42150407798002223
333 45087717511058478
334 48225055074623020
335 51575733183063381
336 55153930189710199
337 58974745796756772
338 63054258892410676
339 67409590336951526
340 72058968237796864
341 77021798716793472
342 82318739554982446
343 87971779934030813
344 94004323496376370
345 100441278174591857
346 107309149839882065
347 114636143468412820
348 122452268693810773
349 130789453710561880
350 139681664205717336
351 149165031568693103
352 159277986855633016
353 170061405064075112
354 181558755982974841
355 193816266501929437
356 206883090422879924
357 220811491009889043
358 235657032087527265
359 251478783301180396
360 268339535105609947
361 286306029500356999
362 305449201822952043
363 325844440053296911
364 347571856673023437
365 370716580000299865
366 395369059764581907
367 421625394343310622
368 449587674134015894
369 479364349022239074
370 511070614115498789
371 544828822282542624
372 580768917352403386
373 619028897134443136
374 659755299786483915
375 703103723360440008
376 749239371713072893
377 798337637330191203
378 850584713900420592
379 906178249959977690
380 965328036082153098
381 1028256737764320020
382 1095200666112868479
383 1166410599374062737
384 1242152647027396400
385 1322709170452985614
386 1408379751496978306
387 1499482223983711007
388 1596353759097684853
389 1699352020801864770
390 1808856381807204423
391 1925269217464240208
392 2049017267678726593
393 2180553085519877265
394 2320356562206788935
395 2468936548541534560
396 2626832562056501613
397 2794616601454368874
398 2972895057192452118
399 3162310741418594367
400 3363545025698964905
401 3577320111503785370
402 3804401421487713028
403 4045600138430032111
404 4301775879480791364
405 4573839534628998805
406 4862756256665494627
407 5169548633773745196
408 5495300031669753174
409 5841158138820994573
410 6208338701343941504
411 6598129483701389567
412 7011894441513529154
413 7451078145408300311
414 7917210441983121567
415 8411911393838459790
416 8936896484567997687
417 9493982133951103748
418 10085091509109124038
419 10712260680430481316
420 11377645107978274030
421 12083526511041755885
422 12832320106588180216
423 13626582273455769130
424 14469018628191675328
425 15362492573908704705
426 16310034308333182605
427 17314850357334785351
428 18380333620521385288
429 19510074000524712510
430 20707869603133059005
431 21977738585689560888
432 23323931641671395577
433 24750945205158909903
434 26263535364084318335
435 27866732572801796923
436 29565857154086910586
437 31366535688534084953
438 33274718282955543138
439 35296696823824161172
440 37439124209176423689
441 39709034673797093666
442 42113865203272523819
443 44661478161286358382
444 47360185128319403266
445 50218772086522051179
446 53246525951955124790
447 56453262600281822770
448 59849356390656452911
449 63445771346214791750
450 67254094000041376472
451 71286568078440378940
452 75556131035169785520
453 80076452623088539474
454 84861975522393894682
455 89927958227838358047
456 95290520220441972408
457 100966689643466790885
458 106974453515430930110
459 113332810718878162162
460 120061827805972476935
461 127182697880305609612
462 134717802605429814419
463 142690777622058656546
464 151126581435179847087
465 160051568077636769428
466 169493563623590070029
467 179481946885287503033
468 190047734380319897611
469 201223669932131414435
470 213044319006514289722
471 225546168178897201877
472 238767729852694651726
473 252749652658529016458
474 267534837674336562975
475 283168560934411337881
476 299698602389599787838
477 317175381828488409051
478 335652101946726064978
479 355184899120000125304
480 375833002095763134994
481 397658899209161246875
482 420728514369579673903
483 445111392477847571669
484 470880894555562555002
485 498114403306277186755
486 526893539429181544859
487 557304389470316520926
488 589437745575705932027
489 623389358002858694117
490 659260200803850999792
491 697156751614571573050
492 737191286017769058224
493 779482187499968819328
494 824154273530537513590
495 871339138876499829930
496 921175516748888083872
497 973809658996595347843
498 1029395736018599697176
499 1088096257722564963285
500 1150082516284160195228
501 1215535052157728174181
502 1284644144185379730847
503 1357610325389379232553
504 1434644925397854279201
505 1515970641235644460006
506 1601822137544568870284
507 1692446678125803856421
508 1788104789995349063877
509 1889070962021415977430
510 1995634379475147217445
511 2108099696756362286402
512 2226787849781318011225
513 2352036910505353502960
514 2484202985239681487827
515 2623661159466440213046
516 2770806491001933879934
517 2926055054465399389878
518 3089845039114165090006
519 3262637903279835837368
520 3444919587699626163784
521 3637201791281150838642
522 3840023311852620267520
523 4053951455769310437411
524 4279583519213134698092
525 4517548345420380827490
526 4768507960989083934055
527 5033159295899948453464
528 5312235990749672570529
529 5606510296267383347695
530 5916795068996439139970
531 6243945868690651790984
532 6588863161730186941949
533 6952494636630048267349
534 7335837636412932897259
535 7739941714493038387800
536 8165911319356988623191
537 8614908615316677008037
538 9088156445187144157315
539 9586941442852234247688
540 10112617302195842515986
541 10666608211114819309586
542 11250412457779475207451
543 11865606218682631897742
544 12513847536400942542792
545 13196880497512645108082
546 13916539619429707920819
547 14674754457577479835276
548 15473554442597974138261
549 16315073960092664254845
550 17201557683591187210221
551 18135366174447279278050
552 19118981760459645860075
553 20155014708216878863814
554 21246209702186282092097
555 22395452646966417293408
556 23605777807066952421208
557 24880375302190809844943
558 26222598973859207708065
559 27635974643056882602957
560 29124208776361246426379
561 30691197582095958536940
562 32341036555756007872574
563 34078030498283984754324
564 35906704028403518436778
565 37831812614821230761958
566 39858354151654428208784
567 41991581105338021975229
568 44237013258729870925770
569 46600451083340332673813
570 49087989767998000853332
571 51706033937801331528663
572 54461313094513716925128
573 57360897815450699974699
574 60412216745139257498220
575 63623074420297550086219
576 67001669965840454287106
577 70556616706287648422219
578 74296962734036669341681
579 78232212483065282718656
580 82372349353645706688557
581 86727859441215163471299
582 91309756419502652632346
583 96129607636065483970326
584 101199561475287452352028
585 106532376052469891973529
586 112141449299494917036082
587 118040850511681791603207
588 124245353422263158954416
589 130770470880651056890508
590 137632491207435568010865
591 144848516309445882213488
592 152436501634954540406115
593 160415298060181677999076
594 168804695794997737313630
595 177625470407537082721000
596 186899431064181789240714
597 196649471093979190555417
598 206899620983325400923391
599 217675103920198163575855
600 229002394004031667131562
601 240909277251684690681991
602 253424915526824874489771
603 266579913535383561990795
604 280406389026693541560050
605 294938046356297019367088
606 310210253563482851100127
607 326260123134106243067899
608 343126596616460516696779
609 360850533276665514506814
610 379474802977432949592235
611 399044383484052797909293
612 419606462399058669164670
613 441210543948397532330378
614 463908560839804564190105
615 487754991436937125672474
616 512806982491007302968677
617 539124477696101694898536
618 566770352332926580196422
619 595810554291880676373224
620 626314251765331338721889
621 658353987926977049814515
622 692005842915643724379123
623 727349603470850543161147
624 764468940567510879673455
625 803451595429252417205137
626 844389574300517873819582
627 887379352392017517121852
628 932522087415520559163978
629 979923843160847259593572
630 1029695823570178794275403
631 1081954617804329189733130
632 1136822456798829611977156
633 1194427481850057437014188
634 1254904025775922313547734
635 1318392907241077114455255
636 1385041738842110913273942
637 1455005249596946472606064
638 1528445622489513098689343
639 1605532847773095680763453
640 1686445092744133077862572
641 1771369088754409127460813
642 1860500536239657243811286
643 1954044528602907498298713
644 2052215995802887756600106
645 2155240168562557730441651
646 2263353064126961916680941
647 2376801994569161652466564
648 2495846098659479051064264
649 2620756898388042485020315
650 2751818881249725985263201
651 2889330109480920434384965
652 3033602857459597799856667
653 3184964278566502763090003
654 3343757102830568648294100
655 3510340366774529838099362
656 3685090176905553914495426
657 3868400508395607218602712
658 4060684040529089811511635
659 4262373030602736307736896
660 4473920227999991634336049
661 4695799830277701282536615
662 4928508483145017415245470
663 5172566326338871474810223
664 5428518087447777097123025
665 5696934225869697000052873
666 5978412129143021176660971
667 6273577364033953219381164
668 6583084984823416367768699
669 6907620901391940912521508
670 7247903309767966876854621
671 7604684187972334672794279
672 7978750860066583292492655
673 8370927631492963904374015
674 8782077498877581534954826
675 9213103937662354632430077
676 9664952771024500351037182
677 10138614123751643890160599
678 10635124464844114878958234
679 11155568742841714328727107
680 11701082617987165623774441
681 12272854795581829794207424
682 12872129465016771712525869
683 13500208849224701210035109
684 14158455869439607508786797
685 14848296930433954412736035
686 15571224831559707174845247
687 16328801809224790058723204
688 17122662716609525949088990
689 17954518346757020946699951
690 18826158905362526710229727
691 19739457639942260837191170
692 20696374632273061911292693
693 21698960761377851861459991
694 22749361844564462300548659
695 23849822964439412250062786
696 25002692990074522611210746
697 26210429300951192075148206
698 27475602722589376993615487
699 28800902683250842418103620
700 30189142601416789879539725
701 31643265514260974333147280
702 33166349957680893422281326
703 34761616109012255792042594
704 36432432203927179785717060
705 38182321239624205783290791
706 40014967976830314258194669
707 41934226253791452214502866
708 43944126625880403790553542
709 46048884345159801497494410
710 48252907694734285262788295
711 50560806693491724240760864
712 52977402187377475447172767
713 55507735344173158008302025
714 58157077569347644255467770
715 60930940861442101638121653
716 63835088626103993911558154
717 66875546968851154044155253
718 70058616487362061237586099
719 73390884585132619407087525
720 76879238329122231766081397
721 80530877875140464242617081
722 84353330485581572874857753
723 88354465165333895253696995
724 92542507942627096595138500
725 96926057822898671250970506
726 101514103444784180025401951
727 106316040468760867890912596
728 111341689730092161485478986
729 116601316189261192310920700
730 122105648714302462837519095
731 127865900731106343903253140
732 133893791779104230080154757
733 140201570011542889312188673
734 146802035681011667815860536
735 153708565652833106920034910
736 160935138990515291014468389
737 168496363659569277404011926
738 176407504397726911089252427
739 184684511801870419745076307
740 193344052683873853814041992
741 202403541750017567604570186
742 211881174660695907633925630
743 221795962529799561823547050
744 232167767925398019655514911
745 243017342436225385867782360
746 254366365870917775402606905
747 266237487160062493722933573
748 278654367033782480744510806
749 291641722550944774278755090
750 305225373558982059563888277
751 319432291166955621416988846
752 334290648317645677016358800
753 349829872548390639201836915
754 366080701033833880689204868
755 383075238007992627776702417
756 400847014666803831752957239
757 419431051656904535008045175
758 438863924260473490012135163
759 459183830390938310034760808
760 480430661518778658401752606
761 502646076652038885173349227
762 525873579500977016616460179
763 550158598962098286585268812
764 575548573062054951632032045
765 602093036508189465718719048
766 629843711998187195057772139
767 658854605448112789933009883
768 689182105304287409515682100
769 720885086111826199264530602
770 754025016519374061539012919
771 788666071907539257156720745
772 824875251835823585246755322
773 862722502511457336756637273
774 902280844491475696422277607
775 943626505838683244008132200
776 986839060960763649685286324
777 1032001575371858971057649812
778 1079200756625292376433262527
779 1128527111676994146896423866
780 1180075110949340867815741705
781 1233943359376888774794645286
782 1290234774726499621066939729
783 1349056773497085149040393990
784 1410521464716153134692849305
785 1474745851964099733658903061
786 1541852043970167239586312161
787 1611967474138865755916722862
788 1685225129379733514094036061
789 1761763788629397872053656235
790 1841728271470168310812182922
791 1925269697266785463516503426
792 2012545755259511142279757939
793 2103720986070547761528308056
794 2198967075098734712886734939
795 2298463158297797109106489154
796 2402396140852894891466543967
797 2510961029292195375886771676
798 2624361277591302806539384785
799 2742809147852133365579270728
800 2866526086160707034443096536
801 2995743114254005523873182447
802 3130701237650846261415731925
803 3271651870929477727256898460
804 3418857280861477088681193790
805 3572591048141530694746914090
806 3733138548481798221217911552
807 3900797453871985260052458844
808 4075878254837797239255661362
809 4258704804565490337503808388
810 4449614885794408992222605768
811 4648960801417270951112899149
812 4857109989764974418889650337
813 5074445665593628197149672976
814 5301367487831589899371459786
815 5538292255188523013383705493
816 5785654630771887697258497283
817 6043907896904068905377662354
818 6313524741380338713964117041
819 6594998076459485958378893765
820 6888841891929819394715899058
821 7195592143649041349226451797
822 7515807679011555533543598553
823 7850071200857049151561981277
824 8198990271393788468402832910
825 8563198357775186443280519481
826 8943355921032697994415593150
827 9340151550138446296778694695
828 9754303143040772965858698738
829 10186559136591896947738953736
830 10637699787362374673765851572
831 11108538505419138541106703326
832 11599923243225576269540370773
833 12112737941910774330966523058
834 12647904037243407637973185275
835 13206382027741516006002444773
836 13789173107444975251914898250
837 14397320865980889208205146211
838 15031913058655481638070586170
839 15694083449417751979187285200
840 16385013729651919315626553903
841 17105935515876284315740117365
842 17858132429546978449201954040
843 18642942262295300491873644125
844 19461759230057983058514364692
845 20316036319700347953181321854
846 21207287731873535854431146036
847 22137091423998816527291292573
848 23107091757424638493951397296
849 24119002252965985500055581660
850 25174608459200593776095715796
851 26275770938073532080602199025
852 27424428372539945976102494714
853 28622600801166781235900298970
854 29872392984806968861002167150
855 31175997910665738676215333083
856 32535700439286901798700622702
857 33953881100209489208178765965
858 35433020042270038972801446267
859 36975701144766017861780518855
860 38584616295938822096005170732
861 40262569845494024660947295511
862 42012483238138973765711468209
863 43837399835397589524492169699
864 45740489933245656295108230276
865 47725055983411775986894981246
866 49794538026495265348750612249
867 51952519345378003110827261245
868 54202732347737800210892356482
869 56549064686822307278421356410
870 58995565629999410845245249221
871 61546452684979235524105543392
872 64206118493988245395946543733
873 66979138006584989785657480428
874 69870275942223081868526029050
875 72884494554108264331119307928
876 76026961706345527347594704821
877 79303059276848230400183285964
878 82718391898965943827138763547
879 86278796055301131921625891170
880 89990349537708001698370213912
881 93859381288020573385341309156
882 97892481634621667732376275773
883 102096512940561692318764350730
884 106478620679545414041204857990
885 111046244956748916027527818266
886 115807132492086385272396343388
887 120769349084240838947935232064
888 125941292574482232140687671573
889 131331706330045205888407419457
890 136949693267603986395677650558
891 142804730438189318931860098564
892 148906684195717827992813143566
893 155265825972174647112602889961
894 161892848683380596389328909468
895 168798883790213584227554656159
896 175995519041114298262612289035
897 183494816922717833662350417491
898 191309333846488659930765021359
899 199452140100326732087685874827
900 207936840595229492504233306945
901 216777596438269801155552535674
902 225989147364354226256328129418
903 235586835060492831290374086887
904 245586627417610185343204061592
905 256005143746292461230858854104
906 266859680994265528704374966390
907 278168241004870074309855533803
908 289949558857309080032590923875
909 302223132331028229051470028105
910 315009252538216762992077236392
911 328329035770124403095575862384
912 342204456604643593166154197584
913 356658382324446662590285111339
914 371714608696857560054084016710
915 387397897168620511892076337672
916 403734013530764870356760850287
917 420749768110901356565795734354
918 438473057552479914783735391765
919 456932908242840263192740301117
920 476159521454251428449155821804
921 496184320264614922255701369227
922 517039998327054611531178692256
923 538760570560285726505201457873
924 561381425834401015587597535976
925 584939381729587005984478601759
926 609472741448241096381760883829
927 635021352964056342627117622190
928 661626670494826928877707482912
929 689331818389061435327715706812
930 718181657519922884138092885125
931 748222854283604706643641918883
932 779503952302948062455752164291
933 812075446940971556454220205991
934 845989862732965181976582851237
935 881301833849962251212020351556
936 918068187710689931737879063981
937 956348031863579681046869065489
938 996202844265034999401543635263
939 1037696567084977431863133956145
940 1080895704175662077477097681300
941 1125869422344946107001489685584
942 1172689656580545105299911876909
943 1221431219377400856365008062125
944 1272171914326045278112412396250
945 1324992654125860472140359971668
946 1379977583193336648931110320432
947 1437214205041903525522823045089
948 1496793514616586528181506509934
949 1558810135773706057762595635280
950 1623362464103023456790431377003
951 1690552815297234404129805536148
952 1760487579281443848700666076840
953 1833277380323323666107694871693
954 1909037243352976817456052905899
955 1987886766730211623716388821460
956 2069950301705885835470684805039
957 2155357138833318717890981357707
958 2244241701595406448756246293607
959 2336743747523122717244801858771
960 2433008577091455559906146902916
961 2533187250689639102003003938112
962 2637436813973694926780915237098
963 2745920531920923374894539658203
964 2858808131917986922455670422595
965 2976276056226732419151647081191
966 3098507724184809838592937106397
967 3225693804511594489967048435217
968 3358032498103807430810629474061
969 3495729831719693225164232556755
970 3638999962965551799845091399647
971 3788065497013976291477983073933
972 3943157815499214466575034483217
973 4104517418051798361058842767460
974 4272394276951864575302865470265
975 4447048205398573802143251956433
976 4628749239911618246836197601280
977 4817778037400144366426924010692
978 5014426287454397541588084311629
979 5218997140436187099507955835990
980 5431805651965752308215752079443
981 5653179244424962571740792903632
982 5883458186119881799298949808463
983 6122996088769755989132217215853
984 6372160424014314043224848431797
985 6631333059657101468251150927444
986 6900910816389260269059601626914
987 7181306045765931733941703701194
988 7472947230236152966218002189763
989 7776279606056958068397836065164
990 8091765809953237435885886484806
991 8419886550416978656059338614377
992 8761141304572662132767573920603
993 9116049041570049084353194338913
994 9485148973501226502442605372510
995 9869001334875809155483171895491
996 10268188191726485611314504174264
997 10683314281456891036071681173407
998 11115007884584932289804712473511
999 11563921729577449985956018909705