0 0
1 0
2 1
3 0
4 2
5 1
6 4
7 3
8 8
9 7
10 15
11 15
12 27
13 29
14 48
15 53
16 82
17 94
18 137
19 160
20 225
21 265
22 362
23 430
24 572
25 683
26 892
27 1066
28 1370
29 1640
30 2078
31 2487
32 3117
33 3725
34 4624
35 5519
36 6791
37 8092
38 9885
39 11752
40 14263
41 16922
42 20416
43 24167
44 29007
45 34254
46 40921
47 48213
48 57345
49 67409
50 79864
51 93661
52 110565
53 129378
54 152211
55 177720
56 208435
57 242841
58 283982
59 330172
60 385048
61 446772
62 519695
63 601810
64 698346
65 807153
66 934477
67 1078081
68 1245439
69 1434250
70 1653485
71 1900860
72 2187108
73 2510097
74 2882686
75 3303003
76 3786497
77 4331767
78 4957324
79 5662539
80 6469625
81 7379025
82 8417451
83 9586876
84 10919379
85 12419090
86 14124570
87 16042787
88 18220175
89 20667498
90 23440611
91 26555314
92 30078859
93 34033500
94 38500307
95 43509870
96 49159850
97 55491569
98 62622735
99 70608195
100 79589941
101 89639934
102 100929358
103 113551768
104 127713611
105 143535339
106 161266026
107 181059683
108 203216653
109 227932736
110 255570108
111 286376132
112 320787614
113 359115589
114 401886567
115 449490061
116 502560604
117 561583847
118 627324401
119 700385675
120 781688468
121 871980197
122 972369363
123 1083778688
124 1207542224
125 1344796017
126 1497144483
127 1665982869
128 1853239823
129 2060624472
130 2290454128
131 2544817742
132 2826497658
133 3138041846
134 3482789043
135 3863840469
136 4285200226
137 4750635850
138 5264945830
139 5832699186
140 6459642645
141 7151307250
142 7914570885
143 8756118323
144 9684174997
145 10706807760
146 11833846685
147 13075011324
148 14442041275
149 15946630703
150 17602788794
151 19424566406
152 21428668907
153 23631955675
154 26054332746
155 28716003578
156 31640669702
157 34852512395
158 38379731364
159 42251233405
160 46500545397
161 51162183158
162 56275976308
163 61883092119
164 68030812518
165 74768183412
166 82151291883
167 90238508372
168 99096314207
169 108794105895
170 119410626856
171 131028298259
172 143740318871
173 157644483177
174 172851016436
175 189475843459
176 207649231291
177 227508466539
178 249207390751
179 272908440444
180 298793165211
181 327053587909
182 357903803027
183 391570608754
184 428306299569
185 468378517958
186 512084362472
187 559739411865
188 611693280508
189 668317761760
190 730023983811
191 797249615814
192 870477788279
193 950223312373
194 1037053543990
195 1131573561479
196 1234449180366
197 1346391032607
198 1468179954984
199 1600649923546
200 1744716060152
201 1901356371973
202 2071642657415
203 2256721001232
204 2457845884851
205 2676359403122
206 2913728914373
207 3171524944887
208 3451462763153
209 3755378943337
210 4085277282800
211 4443304019575
212 4831798555780
213 5253267329987
214 5710439875272
215 6206241361006
216 6743854564889
217 7326691134398
218 7958460114083
219 8643137993831
220 9385044522840
221 10188811638305
222 11059467371062
223 12002403802787
224 13023469957324
225 14128938968291
226 15325610973459
227 16620779722698
228 18022346599821
229 19538786982749
230 21179276644613
231 22953658239642
232 24872581506278
233 26947470332434
234 29190678338513
235 31615457099816
236 34236128870459
237 37068056644460
238 40127836019052
239 43433267906819
240 47003571761998
241 50859361941587
242 55022884781146
243 59517999771892
244 64370443305367
245 69607816039521
246 75259876456924
247 81358536071022
248 87938186320532
249 95035703533494
250 102690813148178
251 110946106672447
252 119847447692234
253 129444003476325
254 139788697776254
255 150938260139858
256 162953731166807
257 175900533081873
258 189849033788909
259 204874642866448
260 221058441542908
261 238487308905767
262 257254625855079
263 277460437053530
264 299212237893638
265 322625178615977
266 347822944444193
267 374938009246179
268 404112620315988
269 435499110050826
270 469260998265534
271 505573371679091
272 544624118252026
273 586614385686580
274 631759964157753
275 680291836658462
276 732457728514988
277 788522764336187
278 848771205000984
279 913507228056285
280 983056875535299
281 1057768977039776
282 1138017334642740
283 1224201810694971
284 1316750779350727
285 1416122404196808
286 1522807389732747
287 1637330477416250
288 1760253534570523
289 1892177301500530
290 2033744859988892
291 2185643668598203
292 2348609458302683
293 2523428598169401
294 2710942471584271
295 2912050220366334
296 3127713661729181
297 3358960465349907
298 3606889678845924
299 3872675399664660
300 4157572985278380
301 4462923290186645
302 4790159646536957
303 5140812745866544
304 5516518486682295
305 5919023591139809
306 6350194428089656
307 6812023466968048
308 7306639198311957
309 7836313540545237
310 8403472995284426
311 9010707137862869
312 9660781161737495
313 10356645600839450
314 11101450436513441
315 11898556218973896
316 12751549931856594
317 13664257701709732
318 14640762639286271
319 15685419350556693
320 16802874000909961
321 17998080868530869
322 19276324908217208
323 20643240618782783
324 22104837417171913
325 23667521126406115
326 25338122508831760
327 27123921719996881
328 29032680392877408
329 31072669446789136
330 33252705162325414
331 35582180783748436
332 38071107078101903
333 40730148224564712
334 43570667411660407
335 46604767568889216
336 49845342623313544
337 53306123698421781
338 57001736726870991
339 60947754819242981
340 65160763014553374
341 69658417608748146
342 74459518919125686
343 79584078460450344
344 85053400705310700
345 90890159105112053
346 97118487947180927
347 103764068340502232
348 110854231402784067
349 118418055468433083
350 126486481986949323
351 135092425364194802
352 144270903119507350
353 154059159943250726
354 164496813845078358
355 175625996203499070
356 187491515844610935
357 200141017074418288
358 213625163858924074
359 227997818070434363
360 243316246197964417
361 259641320308035603
362 277037750002655518
363 295574308895382041
364 315324094856502060
365 336364785140704899
366 358778928318241141
367 382654231565840543
368 408083888083570776
369 435166900478957651
370 464008447917130698
371 494720249995207347
372 527420978372138015
373 562236666052261767
374 599301168797701083
375 638756625321424002
376 680753974406049498
377 725453472155434556
378 773025271435146525
379 823650003055610266
380 877519424920203259
381 934837074819269691
382 995818997531196121
383 1060694477805437684
384 1129706854618327447
385 1203114343925564889
386 1281190950339853291
387 1364227390348910410
388 1452532112869032382
389 1546432334867419812
390 1646275183566113014
391 1752428857792047261
392 1865283906075557162
393 1985254528591872024
394 2112780007034722767
395 2248326163727561347
396 2392386960972062168
397 2545486135816129487
398 2708178988600845676
399 2881054213994558812
400 3064735900713315785
401 3259885581790978540
402 3467204469950063386
403 3687435752703878935
404 3921367090636000334
405 4169833185848465247
406 4433718573500189813
407 4713960495358927789
408 5011552018383093940
409 5327545248740853301
410 5663054815035073693
411 6019261462157244087
412 6397415940993946295
413 6798843025931489407
414 7224945857587357937
415 7677210432722591031
416 8157210451765596739
417 8666612335373638805
418 9207180634316237199
419 9780783633015427358
420 10389399385790506301
421 11035121974465130019
422 11720168242114895240
423 12446884779326468721
424 13217755434511246125
425 14035409111719175614
426 14902628145365622536
427 15822357001729428563
428 16797711615680803626
429 17831989098222772308
430 18928678143608755001
431 20091469856628504664
432 21324269350473853714
433 22631207820044262820
434 24016655464185005171
435 25485234945220145544
436 27041835783888095061
437 28691629360748191595
438 30440084948421427050
439 32292986427621652165
440 34256450139344645202
441 36336943507217490308
442 38541304912253395925
443 40876764434190006315
444 43350965973539493466
445 45971990347814152201
446 48748379910079319619
447 51689164261673527985
448 54803887643565590596
449 58102637555630512758
450 61596075227089693196
451 65295467463891724804
452 69212720537681199036
453 73360415617666205193
454 77751846454251108485
455 82401058790302607100
456 87322892256155433865
457 92533024197802833733
458 98048016244849097301
459 103885363040265591328
460 110063543992467477804
461 116602077443363867761
462 123521578170561324320
463 130843817588012875655
464 138591787624942118816
465 146789767617019867471
466 155463395255556769134
467 164639740897436521410
468 174347386352088911139
469 184616507416073965474
470 195478961347046633003
471 206968378514664842157
472 219120259500987571260
473 231972076854108528604
474 245563382854055586989
475 259935922460149042569
476 275133752891458219556
477 291203368974347380119
478 308193835807954472807
479 326156927845832555776
480 345147276050899251456
481 365222522185728986549
482 386443482009264139042
483 408874316405494093138
484 432582712337329556317
485 457640072614598531977
486 484121716500399166078
487 512107090108174244934
488 541679988754281101579
489 572928790182145382669
490 605946700973590419977
491 640832015027682499688
492 677688386584587733535
493 716625116639860083404
494 757757455400503869728
495 801206919594473936445
496 847101627471698502315
497 895576650276062478872
498 946774383227097412594
499 1000844934760560651413
500 1057946537282324250150
501 1118245978156963211475
502 1181919054417360783552
503 1249151049891926544324
504 1320137238485171744957
505 1395083412287073568263
506 1474206438515327093782
507 1557734843949086038960
508 1645909431147116031052
509 1738983925097233813289
510 1837225654900920840382
511 1940916269134250696728
512 2050352489823913421572
513 2165846903680726676910
514 2287728795890214270468
515 2416345025111961571594
516 2552060945376164748181
517 2695261373547714045795
518 2846351608465399890338
519 3005758500455901770702
520 3173931577782183037298
521 3351344228767469750817
522 3538494946642072634831
523 3735908635909660742515
524 3944137987806433590038
525 4163764923721040534108
526 4395402114716676202042
527 4639694576112329713159
528 4897321345877910308379
529 5168997245909589798207
530 5455474735602485222524
531 5757545856919209889056
532 6076044281087090527354
533 6411847456280431276298
534 6765878867194093336010
535 7139110406051473999002
536 7532564866789309233473
537 7947318562181451835486
538 8384504076548249658317
539 8845313154068961062282
540 9330999736321900372752
541 9842883149365554111358
542 10382351455043597154863
543 10950864967168111415735
544 11549959948409244749758
545 12181252488937125388597
546 12846442583884153757823
547 13547318411121229210331
548 14285760827758620175356
549 15063748087375366199485
550 15883360797842108902391
551 16746787122321125158509
552 17656328244883925784651
553 18614404103987359344101
554 19623559416955817893453
555 20686469999453426693669
556 21805949404944294178931
557 22984955888962723830200
558 24226599725197674210138
559 25534150879156758547238
560 26911047068589555080169
561 28360902217495582635786
562 29887515335256285414221
563 31494879828905489904275
564 33187193282637453476179
565 34968867713898782695995
566 36844540342940813507575
567 38819084886668241936062
568 40897623416674888585537
569 43085538793965991416784
570 45388487723529826564469
571 47812414443113827623111
572 50363565092920143689277
573 53048502782643567303169
574 55874123406423825652868
575 58847672224436583005623
576 61976761265883981231502
577 65269387574667985330799
578 68733952357057168266674
579 72379281055472744479884
580 76214644412647145717731
581 80249780553435671730329
582 84494918153904715853911
583 88960800728475380241337
584 93658712110581443678550
585 98600503161496685847727
586 103798619789132409732448
587 109266132315751797427681
588 115016766283295033606950
589 121064934740010097338971
590 127425772104576164074887
591 134115169656664478190823
592 141149812758269695015819
593 148547219860557427959153
594 156325783409417938072630
595 164504812710877448538177
596 173104578879187721022758
597 182146361935814981535429
598 191652500192621871174001
599 201646441995261379983043
600 212152799971466452994984
601 223197407868850895275016
602 234807380139293413278606
603 247011174363992949645133
604 259838656689741911836739
605 273321170380937954442248
606 287491607672538583907172
607 302384485039963748556692
608 318036022087095965750660
609 334484224181020146306504
610 351768969051999680573973
611 369932097501230076805507
612 389017508453739632300214
613 409071258514259553706553
614 430141666283966857354242
615 452279421612716407199933
616 475537700067007314649862
617 499972282806749482275642
618 525641682175385508177652
619 552607273216694496297137
620 580933431449285122609525
621 610687677134346624300620
622 641940826396448882140289
623 674767149457369087780272
624 709244536374057870778607
625 745454670567500244363069
626 783483210567668030700306
627 823419980290686658428065
628 865359168310502951088664
629 909399536473374415569325
630 955644638357828267207211
631 1004203047963700697462284
632 1055188599176826531067195
633 1108720636431658025295229
634 1164924277166179304785907
635 1223930686533753077950075
636 1285877365018278530132460
637 1350908449463684121086615
638 1419175028220733989308506
639 1490835470972957853994508
640 1566055774006274377867966
641 1645009921539705899380774
642 1727880263948776510304245
643 1814857913559820198403629
644 1906143158919721253104768
645 2001945898285861233564166
646 2102486093320152466892944
647 2207994243804718995184004
648 2318711884449454785860294
649 2434892104688612481966651
650 2556800092630607890423893
651 2684713704145208429259807
652 2818924058354518722047288
653 2959736160607040281676292
654 3107469554312444024667249
655 3262459002820265792475680
656 3425055202841174380077970
657 3595625530707575084875907
658 3774554823103850462786232
659 3962246193687038572346052
660 4159121887371474316161005
661 4365624173833656986233945
662 4582216282166675831439752
663 4809383378388368756201765
664 5047633587902032677057827
665 5297499064775334842998849
666 5559537110120603813584446
667 5834331341618396480868493
668 6122492916668049036760992
669 6424661811399444558741063
670 6741508158247810924239320
671 7073733644535638018966840
672 7422072975000738986412578
673 7787295400943476496829410
674 8170206319190154807401363
675 8571648943795297173545808
676 8992506053960353090075692
677 9433701821363857351919444
678 9896203720685654071279892
679 10381024526817110814620892
680 10889224402871654292257133
681 11421913082811226274038647
682 11980252153163666100915655
683 12565457437999419023330846
684 13178801492034712509932546
685 13821616206414087843621319
686 14495295532465743520004101
687 15201298328401534351601220
688 15941151334718525895419175
689 16716452283730393037985483
690 17528873149489335681787937
691 18380163544024013393936758
692 19272154266701749206828425
693 20206761013182046549794906
694 21185988251364820311098510
695 22211933271390122861494285
696 23286790417739580202155165
697 24412855511138447513984104
698 25592530469011413232078059
699 26828328132890136227580471
700 28122877312289472054138601
701 29478928054211338437080399
702 30899357148623136173948260
703 32387173879897896667037250
704 33945526035464827452943444
705 35577706182558724918208876
706 37287158225296616301760949
707 39077484253950790671771405
708 40952451699710865902352169
709 42916000807870986472470429
710 44972252443890897702659754
711 47125516246427603603293091
712 49380299143042094273756843
713 51741314243940200613822827
714 54213490130815930709616370
715 56801980557529177437233920
716 59512174581167347002949885
717 62349707141715591652010257
718 65320470110493690130730264
719 68430623827207293999351021
720 71686609147518183107409231
721 75095160022745669712164274
722 78663316635500211882242319
723 82398439114779265753292443
724 86308221856385364369146674
725 90400708474280907490734893
726 94684307410974839389890982
727 99167808234820913594298399
728 103860398654749072603352916
729 108771682282770999583237576
730 113911697177415025268339825
731 119290935201105618332535320
732 124920362227501088377390197
733 130811439234709777487611328
734 136976144323500546432764549
735 143426995699583325681509335
736 150177075662441960162053335
737 157240055643222258791963092
738 164630222337810363790630481
739 172362504981326103781508614
740 180452503814129853351707038
741 188916519789608802405751037
742 197771585578141138814900338
743 207035497921891711836833721
744 216726851399502440082094760
745 226865073660094293666920102
746 237470462190704189967218178
747 248564222681744081817108118
748 260168509060094025796494637
749 272306465260028346728212994
750 285002268807539289077181644
751 298281176294347524459058231
752 312169570823619391732713578
753 326695011510288990627843798
754 341886285125005288683550102
755 357773459971772998210772685
756 374387942095897822363632545
757 391762533920084304819824828
758 409931495413526557748926123
759 428930607900279240960373250
760 448797240620671084198869408
761 469570420161202115289265527
762 491290902876358699194607553
763 514001250427715494685291367
764 537745908574242195524297520
765 562571289349950638399372233
766 588525856774163088179355127
767 615660216242211934040161865
768 644027207754166453071067285
769 673682003142055040106976267
770 704682207466523957259622118
771 737087964757124169290887047
772 770962068281628321447424679
773 806370075533445727442174343
774 843380428138206008364429551
775 882064576884703997776216061
776 922497112098252166716728589
777 964755899579109443112093791
778 1008922222342422843295856209
779 1055080928401290000572873427
780 1103320584849299964158487066
781 1153733638504683001691154939
782 1206416583394004180473623027
783 1261470135359767801428098643
784 1318999414093237132165822219
785 1379114132900927348008934154
786 1441928796531384868458267916
787 1507562907396808519816182376
788 1576141180543532173206582127
789 1647793767734192987065052671
790 1722656491025280533362061438
791 1800871086233508574801725662
792 1882585456706834829561358938
793 1967953937826729164782054849
794 2057137572692300205639376184
795 2150304399448788075094681686
796 2247629750748688752819078164
797 2349296565846897900008396022
798 2455495715858899615054163721
799 2566426342725483234274705521
800 2682296212457130455209682301
801 2803322083247128021860301749
802 2929730089074294482596610230
803 3061756139433707944219109307
804 3199646335867993388861400180
805 3343657405990953062043885358
806 3494057155732010316411209027
807 3651124940551041670295894578
808 3815152156412564380917909918
809 3986442751331396320031090525
810 4165313758344208192491383042
811 4352095850786762229080374523
812 4547133920802066232889543439
813 4750787682032464962961725279
814 4963432297497494814901042986
815 5185459033689750400646950878
816 5417275941973440820576643277
817 5659308568403593534814498787
818 5912000693140193785246893892
819 6175815100667931840415269815
820 6451234382092758037646474886
821 6738761770826201158332395144
822 7038922013033450628243820538
823 7352262274264618790862036411
824 7679353083758505843732056313
825 8020789317955578597645146750
826 8377191224832012501351675000
827 8749205490718345916242592021
828 9137506351347064854792157958
829 9542796748929812636730830162
830 9965809537151748723580607512
831 10407308736032029409877712713
832 10868090838692736040105647290
833 11348986172145524592073764023
834 11850860314305644751919387099
835 12374615569515886742778395823
836 12921192504970946070322650602
837 13491571550512068026856107087
838 14086774664377900777381064399
839 14707867067583858944970307584
840 15355959049727123427116168496
841 16032207849108361025023717254
842 16737819610195497531327081346
843 17474051421557050747445203107
844 18242213437536926940202110308
845 19043671087053652808659284262
846 19879847373062334998189389008
847 20752225266338338753939911316
848 21662350197408755583240880783
849 22611832650588854359069697815
850 23602350864260446235126495917
851 24635653641671500654398925083
852 25713563276729711523149554592
853 26837978599417327487235008395
854 28010878145662590152159810428
855 29234323456670946084954212377
856 30510462512943018430585046728
857 31841533308388431557881044984
858 33229867570185399985728912283
859 34677894630233549890123954248
860 36188145454306557202574388848
861 37763256835225448754757362472
862 39405975756652225835411180805
863 41119163934335792443344704400
864 42905802541942186789511630049
865 44768997128852959886162229538
866 46711982737638385763096528557
867 48738129229185132451787393053
868 50850946823805432718899266364
869 53054091866950538300585031212
870 55351372828525098067354342383
871 57746756545119479784050131152
872 60244374714879379386767827687
873 62848530655079053390307968365
874 65563706332897476479764721910
875 68394569680272463189766297406
876 71345982204173741289565113594
877 74423006904042745772669659257
878 77630916508648351397820496666
879 80975202045048066034026549330
880 84461581752883865900268671007
881 88096010357718352732822872833
882 91884688717697696823235490007
883 95834073858343402819578939713
884 99950889410899980761370641448
885 104242136470223354751459537373
886 108715104888867523484723197072
887 113377385024630257366504406314
888 118236879959542565453568602943
889 123301818208939059073746575418
890 128580766940025459691713909256
891 134082645720064896462791085839
892 139816740815143133112243475498
893 145792720061235446782824176425
894 152020648330200268380498354906
895 158511003614148965433422157923
896 165274693752612289015140808752
897 172323073827814816485917108554
898 179667964254413844303535009856
899 187321669591021757420219680979
900 195296998101955629406041512220
901 203607282098697766413213005680
902 212266399091761288370901359750
903 221288793784778242716327895727
904 230689500943930282497695105998
905 240484169177055305874355692001
906 250689085658165140558506398799
907 261321201834419704587978013509
908 272398160154111431736417145946
909 283938321855628636334981918062
910 295960795858989605944065999238
911 308485468803066768245922835517
912 321533036273366843384456918290
913 335125035266881875392335428495
914 349283877942405400158008646518
915 364032886706487833964612979233
916 379396330687227379078362638332
917 395399463650013549856453646567
918 412068563411516287659338756108
919 429430972810286326677893291360
920 447515142294673603715945066211
921 466350674191006819770460000539
922 485968368717496142141128247269
923 506400271811733595200496164655
924 527679724842375737231266747187
925 549841416278195604166136639345
926 572921435390606540910474058430
927 596957328068567354822958679098
928 621988154827914956556778319305
929 648054551100197607653062107591
930 675198789889456373623338078215
931 703464846888666370985168341355
932 732898468151179525914189986678
933 763547240416029756122388501125
934 795460664189866502719632961349
935 828690229692076473525187931906
936 863289495773854029879023167754
937 899314171926070330251169435483
938 936822203495309678417687282049
939 975873860231849535526163798806
940 1016531828298220614442249962790
941 1058861305871734095043466084365
942 1102930102479590217287446438082
943 1148808742210301836140535851762
944 1196570570950788538295878699796
945 1246291867804013007271416393101
946 1298051960848077719508039467334
947 1351933347403643050759093971977
948 1408021818983030424644005817432
949 1466406591100776445263814160960
950 1527180438132396795904965553772
951 1590439833415015131074161499478
952 1656285094791031974866811360028
953 1724820535803436637143476767835
954 1796154622759451260473000642711
955 1870400137887195867483343663479
956 1947674348818757975811284148556
957 2028099184641665059034390886863
958 2111801418770106828781319479052
959 2198912858896530385754825448277
960 2289570544294282737460814459025
961 2383916950751962466780814992085
962 2482100203430948887913450214328
963 2584274297948329076485716205235
964 2690599329999061021500436038470
965 2801241733842785478952460015112
966 2916374529993188620303107718638
967 3036177582460275958549900591156
968 3160837865909343983292204057738
969 3290549743113844726677925853059
970 3425515253093770410318767221243
971 3565944410345615759117092557667
972 3712055515585488127090583947762
973 3864075478442464163613231149415
974 4022240152555965067635501887004
975 4186794683547631350423026868334
976 4357993870356098110318499846416
977 4536102540441049177637214908666
978 4721395939382187638681562911750
979 4914160135418100765087423122503
980 5114692439490694653737304219243
981 5323301841381679202938758660492
982 5540309462549825762653894184386
983 5766049026300099024712773581021
984 6000867345939664937088791408995
985 6245124831599846670745696044057
986 6499196016428781793500363583633
987 6763470102885420757696379238375
988 7038351529893100173383058481177
989 7324260561638762893737209921051
990 7621633898833543447415863970966
991 7930925313280372272554935387934
992 8252606306626103024306289237093
993 8587166794207853854298623978384
994 8935115814937470853337342098638
995 9296982268202626864515370247477
996 9673315678799826600145300908513
997 10064686990951791241951691323923
998 10471689392501180458815902270098
999 10894939170412601125741005524631
1000 11335076598757263951084736380924