0 0
1 1
2 1
3 2
4 3
5 6
6 8
7 13
8 18
9 26
10 36
11 50
12 68
13 92
14 123
15 162
16 214
17 279
18 360
19 464
20 595
21 754
22 959
23 1206
24 1513
25 1893
26 2358
27 2918
28 3615
29 4451
30 5462
31 6691
32 8174
33 9940
34 12081
35 14631
36 17675
37 21314
38 25637
39 30763
40 36861
41 44059
42 52555
43 62600
44 74417
45 88287
46 104600
47 123716
48 146069
49 172228
50 202741
51 238317
52 279760
53 327942
54 383870
55 448817
56 524053
57 611119
58 711809
59 828126
60 962290
61 1116994
62 1295093
63 1499980
64 1735487
65 2005886
66 2316041
67 2671621
68 3078749
69 3544556
70 4077113
71 4685464
72 5379734
73 6171556
74 7073868
75 8101270
76 9270400
77 10599595
78 12109778
79 13824434
80 15769838
81 17975433
82 20474567
83 23304158
84 26505996
85 30126593
86 34218367
87 38839334
88 44055355
89 49938831
90 56571752
91 64044921
92 72460312
93 81930605
94 92583174
95 104557835
96 118012502
97 133120975
98 150078686
99 169100778
100 190429281
101 214329993
102 241101455
103 271072108
104 304609808
105 342118992
106 384052793
107 430908385
108 483242131
109 541665372
110 606860294
111 679576278
112 760649347
113 850996800
114 951640838
115 1063703506
116 1188432918
117 1327198761
118 1481523420
119 1653076639
120 1843712084
121 2055463244
122 2290584077
123 2551546811
124 2841089530
125 3162213999
126 3518241030
127 3912811175
128 4349947357
129 4834058762
130 5370013166
131 5963143631
132 6619333104
133 7345024925
134 8147319917
135 9033993290
136 10013606356
137 11095530700
138 12290076607
139 13608526237
140 15063282533
141 16667913598
142 18437322284
143 20387806682
144 22537256267
145 24905226970
146 27513169276
147 30384524338
148 33544985493
149 37022621457
150 40848177204
151 45055226101
152 49680522005
153 54764185083
154 60350105466
155 66486178380
156 73224768930
157 80622996528
158 88743277793
159 97653670346
160 107428498911
161 118148777830
162 129902935275
163 142787314594
164 156907026945
165 172376550662
166 189320707596
167 207875400266
168 228188738846
169 250421911611
170 274750506341
171 301365543986
172 330475005467
173 362305074231
174 397101900869
175 435133070003
176 476689667463
177 522088009654
178 571672028706
179 625815340906
180 684924010636
181 749438970195
182 819839256333
183 896644855330
184 980420437792
185 1071778739287
186 1171384880618
187 1279960322359
188 1398287913150
189 1527216513547
190 1667666832370
191 1820636882031
192 1987208740531
193 2168554907609
194 2365946182857
195 2580759092805
196 2814484989106
197 3068738778055
198 3345269439227
199 3645970183482
200 3972890697861
201 4328248962223
202 4714445397198
203 5134076690024
204 5589952148202
205 6085109756702
206 6622835158071
207 7206680314861
208 7840485416318
209 8528400632048
210 9274911422137
211 10084863742098
212 10963493381628
213 11916455183321
214 12949856869403
215 14070293023156
216 15284884114385
217 16601315816087
218 18027884141440
219 19573540938342
220 21247945904090
221 23061519332042
222 25025502060037
223 27152016402063
224 29454135356447
225 31945952994808
226 34642664122863
227 37560645709015
228 40717548581441
229 44132391341782
230 47825666054636
231 51819446549877
232 56137509945208
233 60805461665598
234 65850875153307
235 71303435847187
236 77195101941764
237 83560270174728
238 90435960443889
239 97862006808778
240 105881269505759
241 114539854553090
242 123887357372938
243 133977115249770
244 144866486770819
245 156617142194437
246 169295383923604
247 182972479930466
248 197725031429280
249 213635355602209
250 230791906894944
251 249289716425043
252 269230874570252
253 290725034822216
254 313889966671381
255 338852133183605
256 365747323706812
257 394721315989150
258 425930600073603
259 459543136449753
260 495739184324462
261 534712169474233
262 576669631043518
263 621834214911642
264 670444755624140
265 722757412414055
266 779046905511545
267 839607814792876
268 904755991379051
269 974830042007447
270 1050192940274847
271 1131233721924050
272 1218369323707794
273 1312046518929234
274 1412744014593784
275 1520974660801890
276 1637287841713326
277 1762271995757943
278 1896557341169222
279 2040818749626578
280 2195778851235790
281 2362211310467796
282 2540944362250541
283 2732864544220662
284 2938920722806690
285 3160128343897747
286 3397574014362564
287 3652420341790177
288 3925911146301946
289 4219376967997209
290 4534240994384435
291 4872025325289777
292 5234357710820227
293 5622978675973613
294 6039749177375808
295 6486658701487290
296 6965833963062583
297 7479548106765851
298 8030230584631663
299 8620477608218443
300 9253063361179955
301 9930951866504372
302 10657309711095009
303 11435519514970074
304 12269194365526692
305 13162193100374173
306 14118636675733260
307 15142925499604196
308 16239757988049919
309 17414150217016221
310 18671456950837728
311 20017393915876544
312 21458061622682084
313 22999970601453857
314 24650068381032818
315 26415768070226580
316 28304978900677268
317 30326138587652527
318 32488247896575456
319 34800907269172000
320 37274355932069732
321 39919513336946169
322 42748023392497319
323 45772301336664623
324 49005583747270868
325 52461981539753704
326 56156536494568436
327 60105281161454989
328 64325302731357623
329 68834810726388910
330 73653209148306457
331 78801172940117148
332 84300729459254189
333 90175344820339983
334 96450015868613019
335 103151367651009882
336 110307757211523630
337 117949383589176983
338 126108404920579906
339 134819062536198679
340 144117813034971141
341 154043468244103587
342 164637344135656914
343 175943418628156688
344 188008499443753342
345 200882401972932303
346 214618138424311881
347 229272118243696585
348 244904361195555864
349 261578723128144547
350 279363135945791869
351 298329861850467515
352 318555763519482801
353 340122590332687311
354 363117282470152860
355 387632293054845859
356 413765930332259017
357 441622720130777430
358 471313790783070618
359 502957280833850027
360 536678771920745519
361 572611747247388430
362 610898078264350874
363 651688540083641127
364 695143358494211820
365 741432789228859675
366 790737732625603889
367 843250384476641603
368 899174926512725038
369 958728257479248942
370 1022140768587201971
371 1089657164481426015
372 1161537333879725711
373 1238057271237242106
374 1319510053997051034
375 1406206877023733713
376 1498478149230316075
377 1596674654268844930
378 1701168780792283740
379 1812355824468399352
380 1930655367800391047
381 2056512740287494228
382 2190400565585384277
383 2332820398594786956
384 2484304459808270837
385 2645417470292683626
386 2816758595370178907
387 2998963500887284830
388 3192706530945915116
389 3398703011554340230
390 3617711689975672385
391 3850537314871654491
392 4098033368009760940
393 4361104953359035917
394 4640711855436283307
395 4937871773538249961
396 5253663744936944939
397 5589231764585261966
398 5945788615741613987
399 6324619920093466713
400 6727088423263093306
401 7154638525417818419
402 7608801074509888329
403 8091198433151490412
404 8603549838447770097
405 9147677067244633634
406 9725510428102463577
407 10339095094059202267
408 10990597799707251466
409 11682313918446092679
410 12416674945861402618
411 13196256407121491976
412 14023786217026020747
413 14902153512838949417
414 15834417991529427864
415 16823819774060579588
416 17873789831622166709
417 18987960999271228469
418 20170179615497452323
419 21424517816296130055
420 22755286526295533254
421 24167049179000084095
422 25664636213116450365
423 27253160380932548998
424 28938032920604443605
425 30724980632636936202
426 32620063917845673450
427 34629695821901335293
428 36760662149702262186
429 39020142700069296143
430 41415733690604483766
431 43955471429155674735
432 46647857309059164507
433 49501884191224595848
434 52527064258275096484
435 55733458411223709310
436 59131707302785266497
437 62733064085984243204
438 66549428982029007655
439 70593385755210383661
440 74878240209630501429
441 79418060805677435195
442 84227721523030210897
443 89322947079317644361
444 94720360644503635918
445 100437534172569494835
446 106493041505163185912
447 112906514382666870620
448 119698701533478521322
449 126891530992265707246
450 134508175835870146301
451 142573123504607368933
452 151112248917283771693
453 160152891566585053998
454 169723936824857716565
455 179855901667793052492
456 190581025070069655496
457 201933363303583922265
458 213948890418735831680
459 226665604165109076215
460 240123637661174502801
461 254365377097687866666
462 269435585816702313955
463 285381535082253608271
464 302253141920118253514
465 320103114377557578649
466 338987104619606655673
467 358963870251243286506
468 380095444325309816105
469 402447314468038554549
470 426088611629673847934
471 451092308939194463002
472 477535431223161123223
473 505499275719651284778
474 535069644605377137801
475 566337089924415141093
476 599397171600469535002
477 634350729184760595171
478 671304168091851003313
479 710369761045640959029
480 751665965565599581546
481 795317758292960045523
482 841456987072426665908
483 890222741674897792624
484 941761744170970528213
485 996228759935198189536
486 1053787030394879800232
487 1114608728607676269475
488 1178875438896157395524
489 1246778661738918350420
490 1318520345272346431632
491 1394313444729684253473
492 1474382511310438655571
493 1558964311946926057335
494 1648308481613758529146
495 1742678209801893699317
496 1842350962971275587405
497 1947619244774115563099
498 2058791396048317202227
499 2176192436561042396793
500 2300164950705760115022
501 2431070019340218881407
502 2569288200193101345619
503 2715220559255077032068
504 2869289755829274541998
505 3031941183908470041992
506 3203644172825715700051
507 3384893250123202559539
508 3576209469885059032153
509 3778141809784115678538
510 3991268640417592440233
511 4216199270517956783212
512 4453575571975616583015
513 4704073688630254566115
514 4968405833165344246492
515 5247322176470136168252
516 5541612834241553529651
517 5852109955638843357233
518 6179689919244413838775
519 6525275641637758098185
520 6889839004364723904438
521 7274403405152098907537
522 7680046439731512144032
523 8107902720720142407205
524 8559166840561018788008
525 9035096485628082023851
526 9537015709200855605390
527 10066318371136569983881
528 10624471752716477101447
529 11213020355288872444902
530 11833589892032956675418
531 12487891482340226526646
532 13177726059068427342331
533 13904988999124948393727
534 14671674988657695886899
535 15479883134365670362417
536 16331822333329997897595
537 17229816914037850780275
538 18176312562232891845129
539 19173882545538591213520
540 20225234251842226815314
541 21333216056785349828745
542 22500824536834274883474
543 23731212044814041450214
544 25027694666010249907449
545 26393760573409879429895
546 27833078801975985439172
547 29349508462380482712971
548 30947108416053695177683
549 32630147434009903789841
550 34403114863462297600529
551 36270731826919281495339
552 38237962980140071018942
553 40310028856091923014934
554 42492418823879534246114
555 44790904692478545421811
556 47211554991087178389841
557 49760749958877640044474
558 52445197279080351596706
559 55271948593418451543317
560 58248416835244308632805
561 61382394420945414038005
562 64682072341719420254299
563 68156060199177479717025
564 71813407230985020768167
565 75663624374266428416263
566 79716707417485495237209
567 83983161293207425461968
568 88474025567388785264594
569 93200901182729100031779
570 98175978517138480788970
571 103412066820475330796075
572 108922625096532034340087
573 114721794499582781990516
574 120824432318960541669159
575 127246147627725399035656
576 134003338676000016998435
577 141113232112427306386132
578 148593924122109817269522
579 156464423572585190128642
580 164744697264720750215140
581 173455717388950502876460
582 182619511293071291230891
583 192259213671733718755112
584 202399121294060953785032
585 213064750390166651983883
586 224282896824188301416663
587 236081699186249128440810
588 248490704943205994466047
589 261540939793340192805411
590 275264980378242649894401
591 289697030510999837044233
592 304873001088587863657627
593 320830593862844469880923
594 337609389253962558814156
595 355250938397576297055025
596 373798859626923844755503
597 393298939599431387769839
598 413799239288388359993578
599 435350205069046107348208
600 458004785140794243676008
601 481818551536608890197788
602 506849827984371719220235
603 533159823895164491352273
604 560812774768225708056897
605 589876089313817349945635
606 620420503611117534122796
607 652520242630970810247527
608 686253189470592986377034
609 721701062661311944073650
610 758949601929210569222796
611 798088762803908721209931
612 839212920491164469440944
613 882421083441861118256727
614 927817117072192706666631
615 975509978108409886383182
616 1025613960053695079096799
617 1078248950295101251406839
618 1133540699394835017166932
619 1191621103132514796753676
620 1252628497893706793613464
621 1316707970024566840118544
622 1384011679803617631337653
623 1454699200708591108736167
624 1528937874690225691267593
625 1606903184194401971827718
626 1688779141710959698223957
627 1774758697659872431934252
628 1865044167465677717679752
629 1959847678706493241841360
630 2059391639267726903697082
631 2163909227469404484613975
632 2273644905183682358346194
633 2388854955001629131546924
634 2509808042560209074112923
635 2636785805186953662756748
636 2770083468076238786439236
637 2910010489262043401445448
638 3056891234713478950479056
639 3211065684935151250099261
640 3372890174521248648097770
641 3542738166173272536696224
642 3721001060764060262720093
643 3908089045097498489755611
644 4104431979092475967702493
645 4310480324192625573011892
646 4526706114889534844276215
647 4753603975326921131398681
648 4991692183046995082684753
649 5241513782027483676203574
650 5503637747259772191909281
651 5778660203213981437427850
652 6067205698647766717173786
653 6369928540319818603877370
654 6687514188289791964933497
655 7020680715600212346165000
656 7370180335267283223856117
657 7736800997631841848836583
658 8121368061264640480202086
659 8524746040755893056450368
660 8947840434874528397323746
661 9391599638730814640809924
662 9857016943745185551246145
663 10345132629387904655198593
664 10857036150838223273316211
665 11393868426888282086779521
666 11956824232617183141497044
667 12547154701553354541421419
668 13166169942261066851368518
669 13815241774497196940929672
670 14495806590321155556835141
671 15209368345770224918368476
672 15957501688970124107931207
673 16741855230800731543542229
674 17564154964517013304135188
675 18426207840997945197843728
676 19329905506600837502938036
677 20277228210895830461617861
678 21270248891886583511431255
679 22311137446647327402279708
680 23402165195666638238067942
681 24545709549541592019008867
682 25744258887057582553179000
683 27000417654074094895611527
684 28316911693062511029696338
685 29696593813561521369855731
686 31142449614278604943476851
687 32657603568023054801149544
688 34245325381159216259480998
689 35909036639766411844716880
690 37652317755239000767196629
691 39478915222602178087443604
692 41392749205413639228326671
693 43397921461711619313051260
694 45498723626115968896130473
695 47699645863831730320670307
696 50005385913006907615560674
697 52420858532595896579646089
698 54951205373643153705456072
699 57601805292663380840962108
700 60378285126623713612089163
701 63286530949862385712048119
702 66332699834179320306037311
703 69523232134236188595787909
704 72864864321382357694561431
705 76364642390004668406040774
706 80029935861562422575802237
707 83868452412536755844536978
708 87888253153678794927843312
709 92097768589102502665328528
710 96505815285022942870485612
711 101121613279203980273469878
712 105954804263542346856263558
713 111015470573588807435211967
714 116314155020287366553762335
715 121861881600707256423251582
716 127670177126149914872845355
717 133751093807637244117528532
718 140117232840532972531333465
719 146781769031814450423626990
720 153758476515407522361205010
721 161061755602916134756194584
722 168706660819136115338330589
723 176708930173828189357865791
724 185085015723459290206016717
725 193852115478887654234458797
726 203028206717392302694958050
727 212632080759910131343591717
728 222683379276976199653165339
729 233202632189538292468564708
730 244211297233673938038315170
731 255731801261144472202097226
732 267787583350821534488230030
733 280403139809178281526651917
734 293604071141402593986334699
735 307417131078118153408483369
736 321870277746350665637300195
737 336992727077099771745202646
738 352815008545839058484726766
739 369369023346309382507291322
740 386688105102269112332069307
741 404807083226254176831721793
742 423762349039063919278588799
743 443591924768453696422242154
744 464335535550573531528734262
745 486034684562864314493410371
746 508732731422609725504147502
747 532474973990955691225028590
748 557308733728159959722808133
749 583283444751926490337731208
750 610450746757132952002414108
751 638864581961870295490566307
752 668581296251711696059900333
753 699659744701300783840680743
754 732161401659937500159894482
755 766150475595621447794210891
756 801694028900240192812004470
757 838862102867031234221762255
758 877727848060366220804268679
759 918367660307061972300520631
760 960861322548092451955454149
761 1005292152799506042372280897
762 1051747158481833938740277781
763 1100317197388044286270999088
764 1151097145571457259500296685
765 1204186072446713340726801115
766 1259687423409199455145559302
767 1317709210290998271288559592
768 1378364209984768844780006686
769 1441770171580692519191634876
770 1508050032376076393916230359
771 1577332143132085615000182859
772 1649750502967741644666258338
773 1725445004297451141679907324
774 1804561688235302922249143401
775 1887253010906849549623562889
776 1973678121127477405745306832
777 2064003149925411206259060963
778 2158401512407316935568514158
779 2257054222484992815657024668
780 2360150221003212284000879875
781 2467886717831022385818243658
782 2580469548502167524818755242
783 2698113546014402524270691419
784 2821042928422764473658027694
785 2949491702887973628576025603
786 3083704086868536766336309659
787 3223934947173398476731619315
788 3370450257621658074828726589
789 3523527576086490925479113131
790 3683456541732539513178225137
791 3850539393289201836651502824
792 4025091509237025723281012069
793 4207441970820328624533489260
794 4397934148836814215527672885
795 4596926315193841036076999770
796 4804792280261754554235252707
797 5021922057096793197199143492
798 5248722553650191740949140827
799 5485618294125681603611225410
800 5733052170695329742432938359
801 5991486226832993662342325318
802 6261402473576335921118810391
803 6543303740081742349573595601
804 6837714559892395698324420711
805 7145182094397552066093624152
806 7466277095021559934599519954
807 7801594905743708155261783133
808 8151756507615437424557866160
809 8517409607009131754585047279
810 8899229769403510572023996693
811 9297921600583874718308430650
812 9714219977212051861008888437
813 10148891328800118337247159769
814 10602734973204821328588233271
815 11076584507845339610428135980
816 11571309258936626144823544467
817 12087815791123295364897526164
818 12627049479995924748437086176
819 13189996150071928866132857250
820 13777683780927959216269490124
821 14391184284279249355679417592
822 15031615354914641342255878866
823 15700142398513330099333964337
824 16397980539491883419034603648
825 17126396712156938944475317678
826 17886711838571442372338120170
827 18680303096679442559027662255
828 19508606282377659171536135582
829 20373118269370322937430009056
830 21275399570798583698671791072
831 22217077006796088951035610389
832 23199846482289651614115421303
833 24225475879537216706712403128
834 25295808070076172000355456768
835 26412764050942358053003009819
836 27578346210215564863466211001
837 28794641727149749342859394427
838 30063826112357397742646625391
839 31388166893736245936604087274
840 32770027454054771127292543988
841 34211871026349298801392278148
842 35716264853532131176798445637
843 37285884518865576493031710967
844 38923518454223139422854244082
845 40632072633335160147313303424
846 42414575457503959561496250127
847 44274182841571758962023545931
848 46214183508235494937729501941
849 48238004499124801233715280162
850 50349216911395189757684160447
851 52551541868936448016209420984
852 54848856737658906388754847886
853 57245201594696089350951416308
854 59744785961753897851524534687
855 62351995813242406595445211382
856 65071400870249276320554395537
857 67907762191852165302946369001
858 70866040075724187614962534021
859 73951402280459853456690264707
860 77169232582541992488806652472
861 80525139681381306752880246679
862 84024966466392528996177453460
863 87674799660623033930896061137
864 91480979856024425550749640992
865 95450111956053419516920201610
866 99589076041908683363467814313
867 103905038679353462674458727209
868 108405464683743411901431623067
869 113098129361573295562680823025
870 117991131247578917631539459431
871 123092905357179964514976321246
872 128412236974829393377280347684
873 133958275999643712731600384131
874 139740551870530175750551101039
875 145768989093899649034072217804
876 152053923397962137311197292408
877 158606118538543710740878452324
878 165436783782343531637374607358
879 172557592094565848321943341170
880 179980699058919093379312118398
881 187718762559070594023853499356
882 195784963251786006901163068589
883 204193025863165399345822737431
884 212957241340618316513237620541
885 222092489894496140610421709421
886 231614264964627252785484939502
887 241538698148376865364208233480
888 251882585128284891068234525948
889 262663412638819750138368177293
890 273899386513329892459673786979
891 285609460853875905029746150398
892 297813368368291028728976614579
893 310531651920544583370667995967
894 323785697342278194949604539320
895 337597767555246687182476398256
896 351991038056331414480751870517
897 366989633818801526076013504067
898 382618667665585932830082520570
899 398904280172483453357977411132
900 415873681161488936350828464915
901 433555192846746957572198873982
902 451978294698070608801451451939
903 471173670089478817555395729792
904 491173254802820667991698166890
905 512010287459267248372867616043
906 533719361954270234067596520527
907 556336481974509680072274687296
908 579899117678391475260246588893
909 604446264624805604290294482934
910 630018505038130463425183800346
911 656658071500864046791580236982
912 684408913168791142197654677495
913 713316764607254890177526079387
914 743429217350903074468408048582
915 774795794293222556307121122191
916 807468027016271911609547556057
917 841499536175270914475979474888
918 876946115057119308774265204444
919 913865816436494782321905767898
920 952319042857935226463367985970
921 992368640477241831839466390625
922 1034079996600662151664081007759
923 1077521141065624725378297513327
924 1122762851612314849172540623855
925 1169878763401103563926122171075
926 1218945482836785444887946536323
927 1270042705866744493327693378828
928 1323253340926568832325135846994
929 1378663636713273410313389974504
930 1436363314973184001639740357872
931 1496445708498685150590933809083
932 1559007904535458879889672715944
933 1624150893809539969452910463776
934 1691979725391508080991457945422
935 1762603667623427292250292766727
936 1836136375342751583000493808728
937 1912696063646341199178000931448
938 1992405688447002753364736165507
939 2075393134084576538430959317486
940 2161791408263572329650392263128
941 2251738844599701536959898723096
942 2345379313068394870050356869578
943 2442862438659532824536622217435
944 2544343828554178736440367002193
945 2649985308151093589146240468382
946 2759955166283257261274170161243
947 2874428409977525812608933214999
948 2993587029123949508001324919167
949 3117620271435165612969361395332
950 3246724928090696176495775852256
951 3381105630475928850569929906638
952 3520975158441072845298723507218
953 3666554760521468028520091720102
954 3818074486577319579700114213346
955 3975773533328240071251309469700
956 4139900603275944202958715400258
957 4310714277527066240696535322028
958 4488483403047397676107382837692
959 4673487494898881418849276649601
960 4866017154031492611592063257069
961 5066374501223694822145969476849
962 5274873627787530215752752774390
963 5491841063677594566893845747092
964 5717616263667211751102696638395
965 5952552112280070326149289106811
966 6197015448191469082393785307251
967 6451387608840153250589324387426
968 6716064996019563703676798369580
969 6991459663246183924502985277776
970 7277999925732612433825414120395
971 7576130993824029589796914906699
972 7886315630788929496215814059189
973 8209034835888370027068203352971
974 8544788553682622851485141046116
975 8894096410570002861193876125760
976 9257498479589892826238241568102
977 9635556074560578856616552560119
978 10028852574662549957713033455946
979 10437994280619417654854658436401
980 10863611303671658605512657638300
981 11306358488583004148440596144283
982 11766916371965580093225673811770
983 12245992177257870610643973795010
984 12744320847739331357720399884116
985 13262666119017045148700045009690
986 13801821632473293699814015836812
987 14362612091218350997573823093358
988 14945894460150288799646336606682
989 15552559211783166311482028415211
990 16183531619566761710144900741086
991 16839773100485040741820565618034
992 17522282608786961425773720431992
993 18232098082772036320948419250963
994 18970297946624436436893590548336
995 19738002669363380962319830213230
996 20536376383054243863022843508202
997 21366628562504284630273803098630
998 22230015768749313606431382644266
999 23127843458723000661405193155213
1000 24061467863589075904771500947905