0 0
1 1
2 1
3 2
4 3
5 4
6 6
7 8
8 12
9 16
10 21
11 30
12 40
13 52
14 72
15 91
16 121
17 159
18 202
19 260
20 335
21 421
22 535
23 674
24 840
25 1052
26 1304
27 1614
28 1996
29 2451
30 3002
31 3674
32 4468
33 5442
34 6592
35 7971
36 9624
37 11584
38 13898
39 16691
40 19947
41 23823
42 28410
43 33782
44 40113
45 47610
46 56302
47 66572
48 78569
49 92547
50 108898
51 127999
52 150093
53 175933
54 205871
55 240544
56 280816
57 327401
58 381138
59 443389
60 515064
61 597654
62 692867
63 802279
64 927957
65 1072448
66 1237918
67 1427695
68 1645029
69 1893498
70 2177615
71 2502168
72 2872277
73 3294603
74 3775684
75 4323222
76 4946456
77 5654800
78 6459303
79 7373060
80 8409174
81 9583769
82 10914952
83 12421381
84 14125879
85 16053730
86 18231118
87 20690468
88 23466426
89 26596372
90 30125165
91 34101189
92 38576240
93 43613312
94 49278413
95 55644760
96 62798449
97 70831050
98 79843544
99 89955065
100 101290255
101 113990307
102 128216333
103 144140851
104 161956184
105 181884015
106 204157427
107 229043060
108 256838086
109 287863968
110 322480142
111 361093006
112 404134375
113 452098117
114 505525646
115 565008808
116 631208241
117 704859531
118 786754096
119 877790703
120 978945837
121 1091296057
122 1216035701
123 1354483971
124 1508072285
125 1678413023
126 1867250527
127 2076517495
128 2308345223
129 2565075720
130 2849266729
131 3163773462
132 3511682961
133 3896422468
134 4321749199
135 4791783696
136 5311039885
137 5884517746
138 6517630104
139 7216382252
140 7987328746
141 8837651549
142 9775225290
143 10808719168
144 11947535205
145 13202081365
146 14583681289
147 16104737971
148 17778843376
149 19620889719
150 21647057993
151 23875204021
152 26324713889
153 29016815298
154 31974735134
155 35223837862
156 38791719914
157 42708723240
158 47007759146
159 51724839581
160 56899291680
161 62573965564
162 68795508510
163 75615040054
164 83087973918
165 91274886849
166 100241798440
167 110060532862
168 120809278354
169 132573456824
170 145445642080
171 159526910533
172 174927201547
173 191765999154
174 210173303147
175 230290766762
176 252271886039
177 276283994828
178 302508806477
179 331143635120
180 362402972917
181 396520025706
182 433747446604
183 474360236050
184 518656582831
185 566960040552
186 619621932874
187 677023549957
188 739577854963
189 807733605809
190 881976810545
191 962834422889
192 1050877909182
193 1146726568311
194 1251050848976
195 1364578164697
196 1488095492003
197 1622455420951
198 1768581397401
199 1927472938090
200 2100211476142
201 2287968590818
202 2492010639236
203 2713708393044
204 2954544709539
205 3216122925332
206 3500176552918
207 3808581038019
208 4143361885089
209 4506709614789
210 4900991108556
211 5328763179649
212 5792788033452
213 6296050293604
214 6841770937974
215 7433430059617
216 8074783880675
217 8769886566974
218 9523114241655
219 10339190030491
220 11223207337445
221 12180664019367
222 13217488253710
223 14340073277526
224 15555313909442
225 16870644051439
226 18294074562896
227 19834244157961
228 21500459149905
229 23302748010528
230 25251916379497
231 27359603791098
232 29638344059341
233 32101640606177
234 34764028051568
235 37641156717219
236 40749874950938
237 44108315562005
238 47735990342983
239 51653901318435
240 55884636387387
241 60452498634295
242 65383629119413
243 70706139071599
244 76450255477834
245 82648485389059
246 89335764289162
247 96549651725794
248 104330514457773
249 112721728383570
250 121769900098254
251 131525109706144
252 142041140073206
253 153375770068020
254 165591047898446
255 178753598496896
256 192934957402006
257 208211929995457
258 224666943657283
259 242388484068663
260 261471503322525
261 282017885727087
262 304136946828323
263 327945965672236
264 353570721866185
265 381146140962587
266 410816904012988
267 442738149268305
268 477076213660086
269 514009421646840
270 553728898481175
271 596439520434970
272 642360824966647
273 691728061161612
274 744793286483599
275 801826535596217
276 863117042931234
277 928974637155280
278 999731098131244
279 1075741720173966
280 1157386928442970
281 1245074008839872
282 1339238933422676
283 1440348401319852
284 1548901857677368
285 1665433806645164
286 1790516187016898
287 1924760927594269
288 2068822655776189
289 2223401678394838
290 2389246976971376
291 2567159612067467
292 2757996206696676
293 2962672711375459
294 3182168400557322
295 3417530218622391
296 3669877208407927
297 3940405498528306
298 4230393399688827
299 4541206936080375
300 4874305711858857
301 5231249237392546
302 5613703452241843
303 6023448000656032
304 6462383672759700
305 6932540503352917
306 7436086345579818
307 7975336064181064
308 8552761105709144
309 9171000072856300
310 9832869565678848
311 10541375998825998
312 11299728081896425
313 12111350155272028
314 12979896175226649
315 13909265031654423
316 14903616307758766
317 15967387462318622
318 17105311931889662
319 18322438439681339
320 19624151350611449
321 21016192794921992
322 22504685522895578
323 24096157800415565
324 25797569582161418
325 27616340409845754
326 29560378925079678
327 31638114736279460
328 33858531479321050
329 36231202766224788
330 38766329916945494
331 41474782177308554
332 44368139352593404
333 47458737593167442
334 50759717092630626
335 54285073827227925
336 58049713802661303
337 62069510893816214
338 66361368216123916
339 70943283754155232
340 75834418989928915
341 81055173137435741
342 86627260930940250
343 92573795600643526
344 98919376926008872
345 105690185091424216
346 112914079154731337
347 120620703241304601
348 128841597813341641
349 137610318400129311
350 146962561540176407
351 156936298704126348
352 167571917183533640
353 178912371575480713
354 191003342558711757
355 203893406343504208
356 217634214277377975
357 232280683518190420
358 247891198052252338
359 264527824210363600
360 282256536693206491
361 301147459777308272
362 321275122740177821
363 342718730731148181
364 365562450791226506
365 389895717682990680
366 415813554891823348
367 443416917083354395
368 472813052400395255
369 504115886411820969
370 537446427973086092
371 572933202160089021
372 610712705088024636
373 650929888880042817
374 693738674262517327
375 739302493591784736
376 787794865242911556
377 839400005034979394
378 894313469153697528
379 952742839214715505
380 1014908445763498168
381 1081044134584829467
382 1151398077503864667
383 1226233633933432116
384 1305830257597562939
385 1390484461873742852
386 1480510838608352017
387 1576243137115380452
388 1678035405835501765
389 1786263203649306321
390 1901324875709353320
391 2023642910487485970
392 2153665371219920414
393 2291867411825800319
394 2438752880540919042
395 2594856019329444186
396 2760743255002732128
397 2937015102485578568
398 3124308171606985671
399 3323297292176530581
400 3534697761249058963
401 3759267722285260003
402 3997810674031018777
403 4251178133834018736
404 4520272445013469560
405 4806049749381725918
406 5109523129313213329
407 5431765931642130682
408 5773915274158756005
409 6137175764316269807
410 6522823418322020547
411 6932209810091132886
412 7366766454728514451
413 7828009442832764770
414 8317544330621778144
415 8837071321169521009
416 9388390724178348283
417 9973408734662815401
418 10594143535234284500
419 11252731744418536581
420 11951435221792556068
421 12692648271933184056
422 13478905235125421762
423 14312888519112695711
424 15197437076471069304
425 16135555359174500843
426 17130422768812457450
427 18185403652584789431
428 19304057835553494010
429 20490151761000865766
430 21747670243425952144
431 23080828879077013507
432 24494087142378468476
433 25992162228608832035
434 27580043638827999217
435 29263008600876241873
436 31046638331430629327
437 32936835203025651023
438 34939840856989964725
439 37062255335930615247
440 39311057241572989554
441 41693625039069180399
442 44217759514489612822
443 46891707475964587537
444 49724186755317691649
445 52724412601569930993
446 55902125487857545673
447 59267620486662381228
448 62831778224289874227
449 66606097541521179757
450 70602729937306412613
451 74834515911120538863
452 79315023249240699290
453 84058587451743429031
454 89080354319606148815
455 94396324878211016682
456 100023402739402649983
457 105979444051320334768
458 112283310115613010725
459 118954922920868794602
460 126015323627035694427
461 133486734243012977854
462 141392622631886410196
463 149757771039813436168
464 158608348276486094996
465 167971985861061320733
466 177877858194340759101
467 188356767086383345836
468 199441230815833742928
469 211165577982239351235
470 223566046345773338101
471 236680887050274120250
472 250550474332098544514
473 265217421157897300352
474 280726701022453975870
475 297125776258660731969
476 314464733144066417605
477 332796424304320932656
478 352176618580465932356
479 372664158951135874673
480 394321128814067975192
481 417213027104500637787
482 441408952655423532545
483 466981798434298668777
484 494008455919639666395
485 522570030399864486965
486 552752067597743118077
487 584644792270514219535
488 618343359350533764021
489 653948118435652067306
490 691564892033502616648
491 731305268588575956291
492 773286910830541484757
493 817633880329222594266
494 864476979032046744519
495 913954108822164183901
496 966210649702841084564
497 1021399857953804782955
498 1079683284984095836445
499 1141231218085366093356
500 1206223144139026312505
501 1274848237618026739448
502 1347305873772249383742
503 1423806168750207903862
504 1504570547638730603279
505 1589832342053103532465
506 1679837418695469374460
507 1774844840624616342428
508 1875127562519128572224
509 1980973162209867039058
510 2092684609819350437364
511 2210581076713159618812
512 2334998786159615150045
513 2466291907978009213211
514 2604833498995971857114
515 2751016492265785236233
516 2905254736869380209114
517 3067984091278014896059
518 3239663572791859495303
519 3420776566058162715808
520 3611832093219888366892
521 3813366149514313695649
522 4025943106830210409904
523 4250157189195677830648
524 4486634023549719570117
525 4736032269758335725949
526 4999045333411458018069
527 5276403166346119626457
528 5568874158337343585492
529 5877267125253478233748
530 6202433398121133772875
531 6545269018347949613036
532 6906717043956324141923
533 7287769973235400450178
534 7689472290529081403886
535 8112923141194865773773
536 8559279141621987355898
537 9029757331277834695038
538 9525638273387702009642
539 10048269312558891566666
540 10599067995804917702598
541 11179525666278742830294
542 11791211237514496125054
543 12435775157442178333322
544 13114953571100714907737
545 13830572692847137840585
546 14584553396872093232859
547 15378916038300108544080
548 16215785515207881006536
549 17097396583879858163740
550 18026099439289793064545
551 19004365574861535074060
552 20034793933493991839144
553 21120117366000021968341
554 22263209410655476854108
555 23467091410232375280948
556 24734939982538253708140
557 26070094862785659359259
558 27476067134037313601329
559 28956547866918314738918
560 30515417186757611287820
561 32156753789899926248442
562 33884844930510686987046
563 35704196901808297668534
564 37619546033661831970758
565 39635870234307687182933
566 41758401100277709584111
567 43992636623365968447420
568 46344354522912219660804
569 48819626234713426443644
570 51424831586076674820932
571 54166674193305087264827
572 57052197613580965942869
573 60088802289404274771291
574 63284263322982338692427
575 66646749121586090680933
576 70184840953429227921072
577 73907553461470353071271
578 77824356177542066942755
579 81945196087222480143584
580 86280521294788716905508
581 90841305842032019225363
582 95639075733760834903861
583 100685936231846178537378
584 105994600474041720428544
585 111578419484060875538393
586 117451413637886473299169
587 123628305656875219596328
588 130124555197965105808646
589 136956395121650077953839
590 144140869512246205018659
591 151695873537948254338597
592 159640195236113946688398
593 167993559316387086882531
594 176776673074936699398341
595 186011274524959983069040
596 195720182842128072039763
597 205927351239916436812873
598 216657922387023142054595
599 227938286488424452287404
600 239796142153453601335077
601 252260560187922877441770
602 265362050440808026354622
603 279132631856214508994999
604 293605905877826392025638
605 308817133365323128709224
606 324803315185536440805352
607 341603276656861158432890
608 359257756019331683886291
609 377809497127661192733352
610 397303346560186489757073
611 417786355352866306952527
612 439307885572537558664213
613 461919721961960370210394
614 485676188884077182609675
615 510634272823347623098813
616 536853750696855239658205
617 564397324249257079714672
618 593330760812837917412173
619 623723040735507958022731
620 655646511776276824035142
621 689177050804732393790964
622 724394233135229809656955
623 761381509854610705937940
624 800226393512024021146867
625 841020652565173119488196
626 883860514976857802659806
627 928846881400423296187905
628 976085548386593937753689
629 1025687442080976973000914
630 1077768862894351167155864
631 1132451741659055110559618
632 1189863907788538227161002
633 1250139370011044700114808
634 1313418610242577572898052
635 1379848891212204912135490
636 1449584578469322366495731
637 1522787477440866329976271
638 1599627186216141430398268
639 1680281464801713693561293
640 1764936621584311082111703
641 1853787917801660863215906
642 1947039990842302383024668
643 2044907297243309029328917
644 2147614576272601620375491
645 2255397335060315347534232
646 2368502356242002613015335
647 2487188229156141852912291
648 2611725905665198062131281
649 2742399281730002701744030
650 2879505805895744563426939
651 3023357115941269175286396
652 3174279704946734946052234
653 3332615618136484268085829
654 3498723181887935320570640
655 3672977766374558526125144
656 3855772583353649374058836
657 4047519520721976999116487
658 4248650015473859148116875
659 4459615966825533605071738
660 4680890691312883174331447
661 4912969921768939959919236
662 5156372852148520792723621
663 5411643230302942146632965
664 5679350500831595458574776
665 5960091000300553093735088
666 6254489207173660713638499
667 6563199048930017458961447
668 6886905268926107283302185
669 7226324855725169702950528
670 7582208537658310684681033
671 7955342345587309809314183
672 8346549246910418568493151
673 8756690854018931723735144
674 9186669210526520573313096
675 9637428658793509897521870
676 10109957792335855191248769
677 10605291496965879374180724
678 11124513084604666478355878
679 11668756523921999358350956
680 12239208772111772345457488
681 12837112212356159282465542
682 13463767201635002365289007
683 14120534733858032064269364
684 14808839223419335353242207
685 15530171414553540967846641
686 16286091422073085044944842
687 17078231909368525050803113
688 17908301409705586160941195
689 18778087797252383967305739
690 19689461914431214947486328
691 20644381362551829783027399
692 21644894462943447803231917
693 22693144396178389707082042
694 23791373527197099595214051
695 24941927924640985154948515
696 26147262082913338490472259
697 27409943855956780812510107
698 28732659612072393857218195
699 30118219619574832257770506
700 31569563673381087795498467
701 33089766973246870348251421
702 34682046264649730610843103
703 36349766253920983935569682
704 38096446309661832508899515
705 39925767463068308483142724
706 41841579720206673753788898
707 43847909700045239571662405
708 45948968612429620028058653
709 48149160590962542154181273
710 50453091396305118598363198
711 52865577506160200582431525
712 55391655608763524285116740
713 58036592517656369131226385
714 60805895526022866880897560
715 63705323219865897888426128
716 66740896770006809325398971
717 69918911723836733889562599
718 73245950318504053099508549
719 76728894338399142258727024
720 80374938540477989736958645
721 84191604672230573400916394
722 88186756108009162668506019
723 92368613130630077170278925
724 96745768886165918760433814
725 101327206041307233039190049
726 106122314173579775777581796
727 111140907926312179624603570
728 116393245961410747535151085
729 121890050744525276837063360
730 127642529198509444595775978
731 133662394262898532677973017
732 139961887398333596588291226
733 146553802076902491404264227
734 153451508300853152004480165
735 160668978194083733612981195
736 168220812712537470289216387
737 176122269521898061909745796
738 184389292092580312046037263
739 193038540064594951696779397
740 202087420936765385175892004
741 211554123137263991056167276
742 221457650534672728734157315
743 231817858451605695477852405
744 242655491245043018235208016
745 253992221520790139331164289
746 265850691051906162713200010
747 278254553474126154222191097
748 291228518834192172989284918
749 304798400070553618222199186
750 318991161508676057494324643
751 333834969457314713997383956
752 349359244995219854402325930
753 365594719041804656829178195
754 382573489809023874708838959
755 400329082736158725350834871
756 418896513012845467165250026
757 438312350800869401519086670
758 458614789269232376815988828
759 479843715562188383038549954
760 502040784824708220611849987
761 525249497415422457684092176
762 549515279441847594878479350
763 574885566759220939743157449
764 601409892579380313075993870
765 629139978842738376025964101
766 658129831512495068266411612
767 688435839957266081545206467
768 720116880594492230642928535
769 753234424975188701898009197
770 787852652497147337375229989
771 824038567942128713599389056
772 861862124040353525384730098
773 901396349274471261201703145
774 942717481143204465013832065
775 985905105115157581096212077
776 1031042299511685843077912839
777 1078215786568434397844525574
778 1127516089935054014078775780
779 1179037698883794676228316374
780 1232879239508040313912068635
781 1289143653204766437390357627
782 1347938382745683361522820574
783 1409375566255437850728669704
784 1473572239427827067764116743
785 1540650546325124660563483649
786 1610737959118963762742503458
787 1683967507147435659988884942
788 1760478015676883959941157721
789 1840414354774137842133191082
790 1923927698710903553830452154
791 2011175796339921308699521370
792 2102323252899630834273992015
793 2197541823724437841493884524
794 2297010720355382063627748262
795 2400916929567875288342655608
796 2509455545853445020736197348
797 2622830117915049913383444057
798 2741253009757477657445207894
799 2864945776979876369747483285
800 2994139558900142001502333276
801 3129075487168546945733828579
802 3270005111553687748160851482
803 3417190843612466538038756708
804 3570906418983853165005468703
805 3731437379078235971385001376
806 3899081572963167434768433340
807 4074149680281259804247813914
808 4256965756068536988951484594
809 4447867798377785909422718728
810 4647208339647178365188538316
811 4855355062794689075569418577
812 5072691443055886167719425434
813 5299617416626772571980188148
814 5536550077214576511963055377
815 5783924401645234390711187950
816 6042194005721751804433116062
817 6311831931578182150344148009
818 6593331467821244899571285842
819 6887207003807197897059097635
820 7193994919453751974467835578
821 7514254512044795671434270178
822 7848568961543389284305747432
823 8197546335991989537207469816
824 8561820638639129718641214588
825 8942052898501786702593005073
826 9338932306138678571324335636
827 9753177396483024939902218896
828 10185537280656422341588837437
829 10636792928765269622162378997
830 11107758505757884604123732211
831 11599282762508532766283555837
832 12112250484378076273114180282
833 12647583999593533513088724935
834 13206244749881376586162395574
835 13789234925889646341450126813
836 14397599170031467462723888427
837 15032426349493275207247895823
838 15694851402256610851020175013
839 16386057259099214371816407640
840 17107276844658097223098572483
841 17859795160763263356444547252
842 18644951455374514679889390247
843 19464141480592880444910817222
844 20318819843351582391957729837
845 21210502452538867303176780059
846 22140769066452676416481862544
847 23111265944645448817935575713
848 24123708608374250157173691219
849 25179884714046054514027899569
850 26281657044216462711162671952
851 27430966620885941707436105122
852 28629835946023841786147469283
853 29880372374449411297683477806
854 31184771624397648308954534434
855 32545321431316949249392451835
856 33964405350658171626329208097
857 35444506715648706466320427516
858 36988212756279694522710649933
859 38598218885984516731386846159
860 40277333162737801493146483596
861 42028480931578985877739585293
862 43854709655832773602493441420
863 45759193944593229392521340472
864 47745240784333462352088394141
865 49816294982816907820685331197
866 51975944833803291832227495339
867 54227928011386814448801372253
868 56576137703142400145945828264
869 59024628991625964158430325532
870 61577625494145933201337172589
871 64239526271117683740892722732
872 67014913013712436130794128183
873 69908557521943723452527861456
874 72925429484760862031646467017
875 76070704574183731104604171292
876 79349772865979799298537146406
877 82768247599879525783476057558
878 86331974292829971838992293424
879 90047040219326987099967206920
880 93919784273403159503975001349
881 97956807227432169886076498545
882 102164982403496246147260142927
883 106551466773684860259898741147
884 111123712506326605315893453816
885 115889478975832906657933303323
886 120856845254507728193489722114
887 126034223105409114745771164525
888 131430370496083981331014037296
889 137054405653777101502902513743
890 142915821683511876380796885929
891 149024501771287364127414763437
892 155390734995485433205171397604
893 162025232770498757827435459665
894 168939145947513040188566055636
895 176144082598354201402893382290
896 183652126509311576383154786482
897 191475856412907627235146841606
898 199628365986651887707106907167
899 208123284648964889666164757891
900 216974799183614488828513630599
901 226197676225231708685693013570
902 235807285639728048991802758564
903 245819624834761125121458548603
904 256251344036735324493085475694
905 267119772572260650226429760376
906 278442946193442095131707992282
907 290239635487905641705764909336
908 302529375416039692907110649868
909 315332496019586962896881808521
910 328670154347402608981354918601
911 342564367645990550934046145377
912 357038047864244537536280110383
913 372115037523740147074631920946
914 387820147007893341425880662192
915 404179193325370744467670136461
916 421219040405243572262572904275
917 438967640983621565314507210620
918 457454080143774189145692539359
919 476708620574147446780094867626
920 496762749611148878182544389545
921 517649228136158285363973326073
922 539402141398860350803741593864
923 562056951841798086179979782045
924 585650554003886389435340828606
925 610221331583626340847575922782
926 635809216745841834349939875041
927 662455751758987497911930882034
928 690204153053379008419383573438
929 719099377794194782726973843799
930 749188193066648538466029638768
931 780519247774481477337746755666
932 813143147356772066050330477356
933 847112531432088994225776381529
934 882482154483142160334826764351
935 919308969699449334408536504446
936 957652216099971827181956315450
937 997573509062352965137632700477
938 1039136934390198841479974000608
939 1082409146054864772463711090442
940 1127459467753370440453642017188
941 1174359998429505181782920681871
942 1223185721910723169435994798055
943 1274014620819267376937729523685
944 1326927794921956941196870692985
945 1382009584089336341335665999327
946 1439347696041326769228453537105
947 1499033339063295668965477492861
948 1561161359883371327287728002790
949 1625830386909109273080979676918
950 1693142979029092881270640215763
951 1763205780192856333355769792741
952 1836129679990555150833699102193
953 1912029980462246411143015813403
954 1991026569375259318023503499202
955 2073244100217207015888408119538
956 2158812179161505504509479477387
957 2247865559271987862389860247027
958 2340544342223221743062242057040
959 2436994187823638029801026966275
960 2537366531639320238614755745264
961 2641818811027597870008692211228
962 2750514699901186674725999662572
963 2863624352555722022439172565268
964 2981324656906014136639252425107
965 3103799497489414523692913683581
966 3231240028608062674479848849780
967 3363844957995835243150410078997
968 3501820841410256287622122238104
969 3645382388564686262098376185240
970 3794752780831647263149481265780
971 3950164001164379303405824177496
972 4111857176700377888308302194975
973 4280082934528139180076110229730
974 4455101771116295214374344079828
975 4637184435923048344710815940524
976 4826612329723146641303722893473
977 5023677918209818266111498583850
978 5228685161449803393472255393156
979 5441949959791341511562586393957
980 5663800616847293293327397772797
981 5894578320198850946465061977662
982 6134637640489325818159379928619
983 6384347049602560139006599214471
984 6644089458646271700711715497133
985 6914262776487616796376820632494
986 7195280489615988764018987550559
987 7487572264136980633797435655600
988 7791584570731301792492310019065
989 8107781333443543884016941215669
990 8436644603197701351109151119731
991 8778675256969838531261985621374
992 9134393723582730154435431393002
993 9504340737123194501194928383801
994 9889078119019915247815799263489
995 10289189589858140291530594727124
996 10705281612047395394944313456712
997 11137984264499893765363912879876
998 11587952150520056956227242132359
999 12055865340150096772425425040469
1000 12542430348262614730337883565337