0 0
1 1
2 2
3 3
4 5
5 6
6 11
7 15
8 22
9 30
10 40
11 56
12 77
13 101
14 135
15 173
16 231
17 297
18 385
19 490
20 622
21 792
22 1002
23 1255
24 1575
25 1951
26 2436
27 3010
28 3718
29 4565
30 5593
31 6842
32 8349
33 10143
34 12310
35 14868
36 17977
37 21637
38 26015
39 31185
40 37316
41 44583
42 53174
43 63261
44 75175
45 89104
46 105558
47 124754
48 147273
49 173525
50 204184
51 239943
52 281589
53 329931
54 386155
55 451220
56 526823
57 614154
58 715220
59 831820
60 966390
61 1121505
62 1300156
63 1505499
64 1741630
65 2012457
66 2323520
67 2679689
68 3087735
69 3554345
70 4087833
71 4697205
72 5392783
73 6185689
74 7089500
75 8118088
76 9289091
77 10619863
78 12132164
79 13848650
80 15796245
81 18004327
82 20506255
83 23338469
84 26543660
85 30167060
86 34262962
87 38887673
88 44108109
89 49995925
90 56633788
91 64112359
92 72533807
93 82010177
94 92669720
95 104650929
96 118114304
97 133230930
98 150198136
99 169229875
100 190568665
101 214481126
102 241265379
103 271248950
104 304801365
105 342324917
106 384276336
107 431149389
108 483502844
109 541946240
110 607162744
111 679903203
112 761002156
113 851376628
114 952050665
115 1064143196
116 1188908248
117 1327710076
118 1482074143
119 1653668665
120 1844347985
121 2056148051
122 2291320912
123 2552338241
124 2841940500
125 3163125394
126 3519222692
127 3913864295
128 4351078600
129 4835271870
130 5371312964
131 5964539504
132 6620830889
133 7346629512
134 8149040695
135 9035833066
136 10015581680
137 11097645016
138 12292341831
139 13610949895
140 15065874417
141 16670689208
142 18440293320
143 20390982757
144 22540654445
145 24908853444
146 27517052599
147 30388671978
148 33549419497
149 37027355200
150 40853229709
151 45060624582
152 49686288421
153 54770336324
154 60356673280
155 66493175255
156 73232243759
157 80630964769
158 88751778802
159 97662728555
160 107438151117
161 118159068427
162 129913904637
163 142798995930
164 156919475295
165 172389790112
166 189334822579
167 207890420102
168 228204732751
169 250438925115
170 274768604820
171 301384802048
172 330495499613
173 362326859895
174 397125074750
175 435157682947
176 476715857290
177 522115831195
178 571701605655
179 625846753120
180 684957372959
181 749474411781
182 819876908323
183 896684817527
184 980462880430
185 1071823752700
186 1171432692373
187 1280011042268
188 1398341745571
189 1527273599625
190 1667727378078
191 1820701100652
192 1987276856363
193 2168627105469
194 2366022741845
195 2580840181788
196 2814570987591
197 3068829878530
198 3345365983698
199 3646072432125
200 3972998992050
201 4328363658647
202 4714566886083
203 5134205287973
204 5590088317495
205 6085253814677
206 6622987708040
207 7206841706490
208 7840656226137
209 8528581302375
210 9275102522181
211 10085065885767
212 10963707205259
213 11916681236278
214 12950095925895
215 14070545636026
216 15285151248481
217 16601598107914
218 18028182516671
219 19573856161145
220 21248278934192
221 23061871173849
222 25025873760111
223 27152408925615
224 29454549941750
225 31946390607023
226 34643126322519
227 37561133582570
228 40718063627362
229 44132934884255
230 47826239640362
231 51820051838712
232 56138148670947
233 60806135438329
234 65851585970275
235 71304185390165
236 77195892663512
237 83561103925871
238 90436839668817
239 97862933703585
240 105882246575460
241 114540884553038
242 123888443077259
243 133978259344888
244 144867692496445
245 156618412354421
246 169296722391554
247 182973889854026
248 197726516681672
249 213636919820625
250 230793554160455
251 249291451168559
252 269232701252579
253 290726957916112
254 313891991306665
255 338854264008737
256 365749566870782
257 394723676655357
258 425933084409356
259 459545750448675
260 495741934479257
261 534715062908609
262 576672674947168
263 621837416509615
264 670448123060170
265 722760953360441
266 779050629562167
267 839611730366814
268 904760108316360
269 974834369944625
270 1050197489544962
271 1131238503938606
272 1218374349844333
273 1312051800816215
274 1412749565173450
275 1520980492399899
276 1637293969337171
277 1762278433057269
278 1896564103591584
279 2040825852575075
280 2195786311155693
281 2362219145337711
282 2540952590045698
283 2732873183547535
284 2938929793929555
285 3160137866534843
286 3397584011986773
287 3652430836071053
288 3925922161489422
289 4219388528587095
290 4534253126185666
291 4872038056472084
292 5234371069753672
293 5622992691950605
294 6039763882095515
295 6486674126247268
296 6965850144195831
297 7479565078510584
298 8030248384943040
299 8620496275465025
300 9253082935757135
301 9930972392403501
302 10657331232548839
303 11435542077822104
304 12269218019229465
305 13162217893936199
306 14118662665280005
307 15142952738857194
308 16239786535829663
309 17414180133147295
310 18671488298300208
311 20017426762576945
312 21458096037352891
313 23000006655487337
314 24650106150830490
315 26415807632060827
316 28305020340996003
317 30326181989842964
318 32488293351466654
319 34800954869440830
320 37274405775006447
321 39919565526999991
322 42748078035954696
323 45772358543578028
324 49005643635237875
325 52462044226816083
326 56156602112874289
327 60105349839666544
328 64325374609114550
329 68834885946073850
330 73653287859526819
331 78801255302666615
332 84300815636225119
333 90175434980549623
334 96450110192202760
335 103151466319055636
336 110307860425292772
337 117949491546113972
338 126108517833796355
339 134819180623301520
340 144117936524786097
341 154043597379576030
342 164637479165761044
343 175943559810422753
344 188008647052292980
345 200882556284128814
346 214618299743286299
347 229272286871217150
348 244904537455382406
349 261578907351144125
350 279363328479614184
351 298330063062758076
352 318555973788329084
353 340122810048577428
354 363117512048110005
355 387632532914332018
356 413766180933342362
357 441622981929358437
358 471314064268398780
359 502957566506000020
360 536679070305298338
361 572612058898037559
362 610898403751884101
363 651688879997206959
364 695143713458946040
365 741433159877895995
366 790738119649411319
367 843250788562528427
368 899175348396088349
369 958728697912338045
370 1022141228360255862
371 1089657644424399782
372 1161537834849962850
373 1238057794119125085
374 1319510599727473500
375 1406207446553365790
376 1498478743590581081
377 1596675274490756791
378 1701169427975813525
379 1812356499739472950
380 1930656072341176721
381 2056513475336633805
382 2190401332423765131
383 2332821198543892336
384 2484305294265418180
385 2645418340678143838
386 2816759503217942792
387 2998964447736452194
388 3192707518433532826
389 3398704041358160275
390 3617712763855472259
391 3850538434667429186
392 4098034535626594791
393 4361106170762284114
394 4640713124699623515
395 4937873096774343005
396 5253665124416975163
397 5589233202595404488
398 5945790114707874597
399 6324621482504294325
400 6727090051725245450
401 7154640222653942321
402 7608802843339879269
403 8091200276484465581
404 8603551759348655060
405 9147679068841113275
406 9725512513742021729
407 10339097267123947241
408 10990600063775926994
409 11682316277192317780
410 12416677403130684127
411 13196258966925435702
412 14023788883518847344
413 14902156290309948968
414 15834420884488187770
415 16823822787115897075
416 17873792969689876004
417 18987964267331664557
418 20170183018805933659
419 21424521360255636320
420 22755290216553481599
421 24167053021441363961
422 25664640213837714846
423 27253164546230421739
424 28938037257084798150
425 30724985147064883742
426 32620068617410232189
427 34629700713903575934
428 36760667241831527309
429 39020148000237259665
430 41415739207068095416
431 43955477170518116534
432 46647863284229267991
433 49501890409405150715
434 52527070729108240605
435 55733465144597398983
436 59131714309169618645
437 62733071376043079215
438 66549436566966297367
439 70593393646562135510
440 74878248419426778124
441 79418069346443402240
442 84227730407729499781
443 89322956321353645667
444 94720370257893471820
445 100437544171702851679
446 106493051905239118581
447 112906525199196103354
448 119698712782720205954
449 126891542690981418000
450 134508188001516289667
451 142573136155347404229
452 151112262071917313678
453 160152905244553715585
454 169723951046458040965
455 179855916453894155239
456 190581040442651931034
457 201933379285114688629
458 213948907032733069132
459 226665621435831345565
460 240123655613852658274
461 254365395758574199975
462 269435605212954994471
463 285381555241961986287
464 302253162872576636605
465 320103136152911280367
466 338987127249525432549
467 358963893768162876613
468 380095468763120598477
469 402447339861711475160
470 426088638015559743697
471 451092336355096099864
472 477535459708164115593
473 505499305314204629558
474 535069675351607262125
475 566337121865700948256
476 599397204782301852926
477 634350763653787028583
478 671304203896731807232
479 710369798236628238005
480 751666004194875011287
481 795317798414758232180
482 841457028742823649455
483 890222784951928088294
484 941761789114997698055
485 996228806608440180082
486 1053787078862455346513
487 1114608778936426484248
488 1178875491155735802646
489 1246778716001272919665
490 1318520401612120035087
491 1394313503224447816939
492 1474382572040363953132
493 1558964374994977806173
494 1648308547066172438760
495 1742678277747591751312
496 1842351033503159891466
497 1947619317987658064007
498 2058791472042884901563
499 2176192515439287461625
500 2300165032574133425735
501 2431070104309287327876
502 2569288288377098289281
503 2715220650772245313220
504 2869289850802400662045
505 3031941282464198651616
506 3203644275096202070012
507 3384893356244349844341
508 3576209579998154653671
509 3778141924035171537110
510 3991268758957922852921
511 4216199393504640098482
512 4453575699570940947378
513 4704073821002175842062
514 4968405970488126319775
515 5247322318923607545026
516 5541612982013113936133
517 5852110108921301661040
518 6179690078238084808000
519 6525275806549652788115
520 6889839175409237584283
521 7274403582551733377346
522 7680046623716094332553
523 8107902911527474124146
524 8559167038437716736150
525 9035096690828663589492
526 9537015921990240021538
527 10066318591787500106586
528 10624471981512075020731
529 11213020592521695111580
530 11833590138005916140074
531 12487891737367521803652
532 13177726323474524612308
533 13904989273245567335012
534 14671675272840783232475
535 15479883428970329919570
536 16331822638729701493803
537 17229817230617210720599
538 18176312890390861435034
539 19173882885687454484110
540 20225234604408667763377
541 21333216422211708570598
542 22500824915577356165493
543 23731212437346370138355
544 25027695072821279146420
545 26393760995004841021914
546 27833079238879849385687
547 29349508915133986374841
548 30947108885217475101876
549 32630147920163234060900
550 34403115367204443779414
551 36270732348871285128752
552 38237963520943177237554
553 40310029416409244587122
554 42492419404397720872600
555 44790905293906338105928
556 47211555614160398040338
557 49760750604354432757376
558 52445197947746313627407
559 55271949286085137715955
560 58248417552751107047851
561 61382395164161775318496
562 64682073111542943380454
563 68156060996536236172174
564 71813408056839596203570
565 75663625229608204067009
566 79716708303343130521599
567 83983162210640880002321
568 88474026517495817981253
569 93200902166643654187580
570 98175979536033019261723
571 103412067875563710992446
572 108922626189067392956037
573 114721795630860408658491
574 120824433490320564237125
575 127246148840550902417850
576 134003339931725153597473
577 141113233412529912746558
578 148593925468119890197615
579 156464424966082817448060
580 164744698707339198675992
581 173455718882380096095248
582 182619512839056823919887
583 192259215272078129526277
584 202399122950629095580175
585 213064752104882879450053
586 224282898599046831034631
587 236081701023305130945921
588 248490706844586261413858
589 261540941761240642265710
590 275264982414932691132499
591 289697032618827122974972
592 304873003269975366031783
593 320830596120295386610807
594 337609391590065169560935
595 355250940815001048889522
596 373798862128436852709430
597 393298942187883251157044
598 413799241966727832978027
599 435350207840317348270000
600 458004788008142464204062
601 481818554503286362923739
602 506849831053734861481872
603 533159827070679866278987
604 560812778053476538349420
605 589876092712500276315813
606 620420507127059714307352
607 652520246268116112057164
608 686253193233019826880477
609 721701066553229757379480
610 758949605954967417784809
611 798088766967999186006767
612 839212924798226411060795
613 882421087896683264554175
614 927817121679723721849795
615 975509982873754244587263
616 1025613964982134990453294
617 1078248955392080004474789
618 1133540704665979618906662
619 1191621108583631746910145
620 1252628503530792664500409
621 1316707975853817969920561
622 1384011685831426958558879
623 1454699206941558115141676
624 1528937881135168275063375
625 1606903190858351526001019
626 1688779148601189609516729
627 1774758704783877366657989
628 1865044174831202682776536
629 1959847686321528964669495
630 2059391647140523709306787
631 2163909235608484556362424
632 2273644913597837330081136
633 2388854963699932382735982
634 2509808051552031608082535
635 2636785814481958737354780
636 2770083477684418110395121
637 2910010499193691843303014
638 3056891244979232231862474
639 3211065695545980277248740
640 3372890185488478058606419
641 3542738177508596708707874
642 3721001072479541451508397
643 3908089057205582486668934
644 4104431991606013700457110
645 4310480337124866626805078
646 4526706128254173781044298
647 4753603989138067267826945
648 4991692197319220372390544
649 5241513796775816319683700
650 5503637762499721779991695
651 5778660218961559003723580
652 6067205714919484306343541
653 6369928557132709817142929
654 6687514205661440172553650
655 7020680733548743500414373
656 7370180353811425547662139
657 7736801016790889035132284
658 8121368081058512888507057
659 8524746061205131302394950
660 8947840456000326196842808
661 9391599660555044587641517
662 9857016966290401433259592
663 10345132652677367520056676
664 10857036174895938656583295
665 11393868451738992947823427
666 11956824258286445517629485
667 12547154728067493595502055
668 13166169969647255482980383
669 13815241802783448943206160
670 14495806619536368856338723
671 15209368375944215483241988
672 15957501720133631304230773
673 16741855262985451980947171
674 17564154997755650263621500
675 18426207875324201406159060
676 19329905542049511423199336
677 20277228247502764885900784
678 21270248929688765106878025
679 22311137485682880566295780
680 23402165235974882359372622
681 24545709591163085124246501
682 25744258930034131533263392
683 27000417698448800353553865
684 28316911738879831363625420
685 29696593860867266773960305
686 31142449663120060247020395
687 32657603618448918933404658
688 34245325433219728719773420
689 35909036693513349075724695
690 37652317810725750308423352
691 39478915279883795756623331
692 41392749264546866860893416
693 43397921522754943172592795
694 45498723689129703063649450
695 47699645928878014105189374
696 50005385980149860746062163
697 52420858601901549459658530
698 54951205445179608281719072
699 57601805366500810491219000
700 60378285202834459545150524
701 63286531028521032840985510
702 66332699915362724119980694
703 69523232218023552371152320
704 72864864407855341219969825
705 76364642479247390302843146
706 80029935953661656574123574
707 83868452507581852374822598
708 87888253251761884175130183
709 92097768690318501305952845
710 96505815389469679436756614
711 101121613386982294887579670
712 105954804374756131323439197
713 111015470688345108146850290
714 116314155138696524440183805
715 121861881722882918263977385
716 127670177252209281782740521
717 133751093937700984130081285
718 140117232974725477106760252
719 146781769170263852819573505
720 153758476658245859053752148
721 161061755750279477635534762
722 168706660971164630122439117
723 176708930330666271859881567
724 185085015885255746880625875
725 193852115645795728075331372
726 203028206889569986197651315
727 212632080937520072186590492
728 222683379460186024851577401
729 233202632378520643600875145
730 244211297428606679192872918
731 255731801462210865865001525
732 267787583558210323920375877
733 280403140023083872114273884
734 293604071362025285843562670
735 307417131305664188565344449
736 321870277981032622582593573
737 336992727319136467572139095
738 352815008795455957133215652
739 369369023603738655757458075
740 386688105367749907671231878
741 404807083500032850651734059
742 423762349321394151918928481
743 443591925059596733749014862
744 464335535850798483634138280
745 486034684872448234756971096
746 508732731741838107613602755
747 532474974320122372524707631
748 557308734067567635805394638
749 583283445101886813536239875
750 610450747117966875338536496
751 638864582333908382360557376
752 668581296635294279311393900
753 699659745096778286894322787
754 732161402067670820574405230
755 766150476015982082122832791
756 801694029333610862568750951
757 838862103313805798709299373
758 877727848520950325159242658
759 918367660781873199488134935
760 960861323037560764797584659
761 1005292153304074193879898920
762 1051747159001957690209588887
763 1100317197924192833923669753
764 1151097146124113726578727360
765 1204186073016374967449180668
766 1259687423996378387111229150
767 1317709210896221493178043552
768 1378364210608578997366598385
769 1441770172223648126550509165
770 1508050033038752430381638446
771 1577332143815074048889599022
772 1649750503671651735806603894
773 1725445005022910006140645612
774 1804561688982956164492944650
775 1887253011677361543335640283
776 1973678121921532286407950000
777 2064003150743712843868729636
778 2158401513250589964731360493
779 2257054223353982965849642005
780 2360150221898687108932534207
781 2467886718753771981901721670
782 2580469549453004933593920862
783 2698113546994164480174756373
784 2821042929432312216467202070
785 2949491703928193307643485523
786 3083704087940340693022764503
787 3223934948277725160271634798
788 3370450258759473520427114109
789 3523527577258789108163787100
790 3683456542940343315611305798
791 3850539394533563994343413787
792 4025091510519029370421431033
793 4207441972141088280734057870
794 4397934150197476827913759850
795 4596926316595586555164745631
796 4804792281705797515062559743
797 5021922058584382849328869242
798 5248722555182613689484387822
799 5485618295704258477069984050
800 5733052172321422397018752513
801 5991486228508002426815719537
802 6261402475301701333080509487
803 6543303741858946450905285538
804 6837714561722963378455094385
805 7145182096283051868548035178
806 7466277096963606051213804496
807 7801594907743960700949000443
808 8151756509675604512522473567
809 8517409609130970421571757565
810 8899229771588828332056013325
811 9297921602834531195851268718
812 9714219979529959777862768265
813 10148891331187245215547993864
814 10602734975663191221223594155
815 11076584510377034212592146134
816 11571309261543787320061392679
817 12087815793808125625662163707
818 12627049482760689878061744701
819 13189996152918959195978870030
820 13777683783859651629656740387
821 14391184287298069419105856949
822 15031615358023124634594092724
823 15700142401714084441377203063
824 16397980542787591098996821750
825 17126396715550358245204466766
826 17886711842065410771034749979
827 18680303100276877491522988120
828 19508606286081561360311437674
829 20373118273183778133458320225
830 21275399574724765260648537424
831 22217077010838260632179411313
832 23199846486451169343993151122
833 24225475883821531494697782922
834 25295808074486832813101046425
835 26412764055483013889288337587
836 27578346214889968804237171486
837 28794641731961759722351371983
838 30063826117310982372086476080
839 31388166898835484452139885750
840 32770027459303858328146065849
841 34211871031752548278772284453
842 35716264859093977687647313415
843 37285884524590579748861394570
844 38923518460115987806848673270
845 40632072639400673501690375209
846 42414575463747094337180792099
847 44274182847997609942310578598
848 46214183514849300594196193732
849 48238004505931946889525421000
850 50349216918401211902779862545
851 52551541876147039010384562987
852 54848856745079917639394818823
853 57245201602333536237114022805
854 59744785969613964515539259105
855 62351995821331449687081289664
856 65071400878573831543609957267
857 67907762200418949875852866531
858 70866040084540107092698343096
859 73951402289532005957331751320
860 77169232591877674259673043664
861 80525139690988018278755885205
862 84024966476277979232856334449
863 87674799670795146675673859587
864 91480979866491345649258758095
865 95450111966823517852557061715
866 99589076052990565170686659417
867 103905038690755971019484297576
868 108405464695475636367939373595
869 113098129373644577851404473535
870 117991131259998858773692884089
871 123092905369958432777075796052
872 128412236987976529870072690275
873 133958276013169939669531019316
874 139740551884446204479331411000
875 145768989108216486627077075021
876 152053923412691097170490155923
877 158606118553696417431847045996
878 165436783797931931934295220337
879 172557592110602218633091543840
880 179980699075416049079342505550
881 187718762576041099642814429720
882 195784963269243383580949581161
883 204193025881123335512830178821
884 212957241359090878236182734445
885 222092489913497780329111772191
886 231614264984172822820073009257
887 241538698168481624527315178361
888 251882585148964518765460484674
889 262663412660090356154504995095
890 273899386535208029003332955682
891 285609460876378579895067651923
892 297813368391435715163322531331
893 310531651944349233813920512829
894 323785697366761254448562966675
895 337597767580427104875211164186
896 351991038082228660789452118410
897 366989633845435601723754690835
898 382618667692977386826261193199
899 398904280200653395819254517900
900 415873681190459054099156974494
901 433555192876539531087229255477
902 451978294728708525214023001725
903 471173670120985588372050797999
904 491173254835220446432862090800
905 512010287492584844397010000527
906 533719361988531136324395159455
907 556336482009740068071399064008
908 579899117714618242279047917300
909 604446264662056374189988834755
910 630018505076433610810502845484
911 656658071540248718776792346785
912 684408913209287275550344075013
913 713316764648893234122621625751
914 743429217393715213042975617565
915 774795794337240928038131467372
916 807468027061529837515792402675
917 841499536221802614337232047468
918 876946115104959930393838357571
919 913865816485680423486405066750
920 952319042908502960931125367378
921 992368640529229737341624411924
922 1034079996654109332431762911842
923 1077521141120571341397403386532
924 1122762851668802145076610697775
925 1169878763459173894661608963191
926 1218945482896482311379736998403
927 1270042705928112564209840426896
928 1323253340989653981276400185806
929 1378663636778122744608506419570
930 1436363315039845895727925635660
931 1496445708567209282036578487803
932 1559007904605896258842021462474
933 1624150893881942976244820893255
934 1691979725465930503404211099660
935 1762603667699924358850181560969
936 1836136375421380008668856717532
937 1912696063727159213943851080855
938 1992405688530070149968413761596
939 2075393134169954709485716047155
940 2161791408351324310932570776876
941 2251738844689892053427982289844
942 2345379313161090374436414551558
943 2442862438754801545567295092897
944 2544343828652090726779455860435
945 2649985308251720768739859839686
946 2759955166386673475403099789409
947 2874428410083806869907819978392
948 2993587029233173241168779714732
949 3117620271547411926979127053250
950 3246724928206047104273245455413
951 3381105630594468612010288127863
952 3520975158562887897616477410546
953 3666554760646647127956344306190
954 3818074486705953843294627812035
955 3975773533460423033024973934767
956 4139900603411771887815710365915
957 4310714277666637214536144927329
958 4488483403190813123215639907302
959 4673487495046245204241629451110
960 4866017154182911352706988350050
961 5066374501379277964399166419563
962 5274873627947390097986152243705
963 5491841063841846500452896053582
964 5717616263835974099255567733750
965 5952552112453464576684381204325
966 6197015448369619941842104648894
967 6451387609023188709970129910797
968 6716064996207615136996693074302
969 6991459663439386169435859778910
970 7277999925931103883841653763584
971 7576130994027952290703815097177
972 7886315630998429231248733036419
973 8209034836103596418058528755338
974 8544788553903729460741526714750
975 8894096410797147285374874542109
976 9257498479823236816318777820416
977 9635556074800288403768986034253
978 10028852574908795418824727341746
979 10437994280872373856676062879735
980 10863611303931504962778081857287
981 11306358488849924787366667765407
982 11766916372239763961801564990016
983 12245992177539511607834487453052
984 12744320848028628464246059627690
985 13262666119314202548127912943478
986 13801821632778520931079437719552
987 14362612091531863067120268402228
988 14945894460472306341153073892017
989 15552559212113915719970799358900
990 16183531619906475293515858641329
991 16839773100833956878604913215477
992 17522282609145324707635966077022
993 18232098083140097717852712346115
994 18970297947002453464660671155990
995 19738002669751617838450919800311
996 20536376383452971700767593594021
997 21366628562913781584556907794729
998 22230015769169865076825741905555
999 23127843459154899464880444632250
1000 24061467864032622469719150698603