0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 21
9 29
10 40
11 53
12 71
13 93
14 122
15 158
16 204
17 260
18 332
19 419
20 528
21 661
22 825
23 1023
24 1267
25 1560
26 1916
27 2344
28 2860
29 3476
30 4217
31 5097
32 6147
33 7393
34 8872
35 10618
36 12685
37 15115
38 17977
39 21336
40 25276
41 29882
42 35271
43 41551
44 48872
45 57385
46 67277
47 78745
48 92040
49 107413
50 125183
51 145688
52 169329
53 196541
54 227850
55 263807
56 305079
57 352388
58 406573
59 468554
60 539411
61 620304
62 712596
63 817780
64 937563
65 1073830
66 1228751
67 1404690
68 1604369
69 1830787
70 2087338
71 2377779
72 2706381
73 3077828
74 3497443
75 3971103
76 4505413
77 5107686
78 5786160
79 6549900
80 7409110
81 8375064
82 9460360
83 10678939
84 12046396
85 13579912
86 15298696
87 17223960
88 19379301
89 21790793
90 24487456
91 27501255
92 30867745
93 34626142
94 38819907
95 43496984
96 48710513
97 54518982
98 60987175
99 68186439
100 76195593
101 85101432
102 94999830
103 105996176
104 118206807
105 131759630
106 146795560
107 163469488
108 181952009
109 202430372
110 225110680
111 250219145
112 278004376
113 308739139
114 342723093
115 380284635
116 421784322
117 467617208
118 518216504
119 574056668
120 635657759
121 703588808
122 778473176
123 860992715
124 951893625
125 1051991752
126 1162179534
127 1283431904
128 1416814735
129 1563492000
130 1724735159
131 1901932053
132 2096597992
133 2310385802
134 2545099159
135 2802704646
136 3085346752
137 3395362583
138 3735299509
139 4107931928
140 4516282317
141 4963641177
142 5453590919
143 5990029867
144 6577200272
145 7219715817
146 7922594816
147 8691292718
148 9531739984
149 10450380824
150 11454217488
151 12550854805
152 13748552376
153 15056276925
154 16483762064
155 18041570208
156 19741162288
157 21594969052
158 23616472822
159 25820290939
160 28222269597
161 30839581940
162 33690837237
163 36796193928
164 40177487141
165 43858360512
166 47864412721
167 52223351697
168 56965164704
169 62122296035
170 67729845003
171 73825772490
172 80451128564
173 87650293110
174 95471239441
175 103965811458
176 113190029582
177 123204412029
178 134074326464
179 145870362981
180 158668740528
181 172551736175
182 187608155514
183 203933828992
184 221632152338
185 240814661044
186 261601653744
187 284122852721
188 308518123643
189 334938237525
190 363545696955
191 394515615712
192 428036670018
193 464312108691
194 503560848992
195 546018639508
196 591939316922
197 641596145264
198 695283260267
199 753317205427
200 816038592517
201 883813866460
202 957037207583
203 1036132559777
204 1121555812920
205 1213797126080
206 1313383431776
207 1420881100387
208 1536898805571
209 1662090580105
210 1797159097940
211 1942859169936
212 2100001503211
213 2269456703374
214 2452159570728
215 2649113682076
216 2861396303852
217 3090163626475
218 3336656382488
219 3602205829560
220 3888240162835
221 4196291352636
222 4528002466489
223 4885135470240
224 5269579587388
225 5683360202136
226 6128648388369
227 6607771068140
228 7123221876531
229 7677672736145
230 8273986242382
231 8915228853288
232 9604684989921
233 10345872063147
234 11142556528067
235 11998770983192
236 12918832444990
237 13907361805745
238 14969304612636
239 16109953203273
240 17334970332197
241 18650414327079
242 20062765945072
243 21578956959959
244 23206400661441
245 24953024331174
246 26827303875823
247 28838300688804
248 30995700965223
249 33309857535902
250 35791834461030
251 38453454491952
252 41307349644384
253 44367015003915
254 47646866062152
255 51162299702522
256 54929759157455
257 58966803109928
258 63292179269864
259 67925902618490
260 72889338720264
261 78205292300117
262 83898101519240
263 89993738216233
264 96519914564731
265 103506196445704
266 110984124073078
267 118987340185512
268 127551726391186
269 136715548067520
270 146519608434140
271 157007412248424
272 168225339853829
273 180222832060056
274 193052586653907
275 206770767135842
276 221437224532158
277 237115732948047
278 253874239855704
279 271785131834785
280 290925516856550
281 311377523980944
282 333228621637320
283 356571955460411
284 381506707039884
285 408138474639400
286 436579677380347
287 466949984146602
288 499376768825150
289 533995593286421
290 570950719964851
291 610395655574068
292 652493728009024
293 697418698235460
294 745355409395575
295 796500475140735
296 851063009743877
297 909265402198376
298 971344137124000
299 1037550665041400
300 1108152325092065
301 1183433323062980
302 1263695768221928
303 1349260772110684
304 1440469613174960
305 1537684970853173
306 1641292233370302
307 1751700883277469
308 1869345965554610
309 1994689642733469
310 2128222842375616
311 2270467002000112
312 2421975917317051
313 2583337699446673
314 2755176847743337
315 2938156444499220
316 3132980478862288
317 3340396307101151
318 3561197257285555
319 3796225386329081
320 4046374398485216
321 4312592734085204
322 4595886838594862
323 4897324621934907
324 5218039119168906
325 5559232363630602
326 5922179484967620
327 6308233044354430
328 6718827620707217
329 7155484661713574
330 7619817614937599
331 8113537354368439
332 8638457919518877
333 9196502584088344
334 9789710273155885
335 10420242348023664
336 11090389779652095
337 11802580731945096
338 12559388578311360
339 13363540375041776
340 14217925817471648
341 15125606705311609
342 16089826945837289
343 17114023124251394
344 18201835673254464
345 19357120674284724
346 20583962325932740
347 21886686115830211
348 23269872735252984
349 24738372776740827
350 26297322258480520
351 27952159020075922
352 29708640038174656
353 31572859711754702
354 33551269170647289
355 35650696662554200
356 37878369078203301
357 40241934675811566
358 42749487070914793
359 45409590559717016
360 48231306848979893
361 51224223268018738
362 54398482543990180
363 57764814224096870
364 61334567834589561
365 65119747869599368
366 69133050709141704
367 73387903569375904
368 77898505595441024
369 82679871210904344
370 87747875845903917
371 93119304170680110
372 98811900969401811
373 104844424794578228
374 111236704551711533
375 118009699169324235
376 125185560519891137
377 132787699763822411
378 140840857299366950
379 149371176508932830
380 158406281504488276
381 167975359082601672
382 178109245113169045
383 188840515595223032
384 200203582627260000
385 212234795550194004
386 224972547536907043
387 238457387913552983
388 252732140515337211
389 267842028392539487
390 283834805200978325
391 300760893625902856
392 318673531209031048
393 337628923964104576
394 357686408189265483
395 378908620902598545
396 401361679351415085
397 425115370066182560
398 450243347957165662
399 476823345973517938
400 504937395874577568
401 534672060687873200
402 566118679460243529
403 599373624936238072
404 634538574833608359
405 671720797415465334
406 711033452098025854
407 752595905866619917
408 796534066314653740
409 842980732157932984
410 892075962123576899
411 943967463153359024
412 998810998912957460
413 1056770819644364544
414 1118020114454096052
415 1182741487180814673
416 1251127457047553119
417 1323380985358796963
418 1399716029570538640
419 1480358126123192071
420 1565545003500278128
421 1655527227044414835
422 1750568877143140915
423 1850948262471439609
424 1956958670067015128
425 2068909154097428548
426 2187125365274455104
427 2311950422963073630
428 2443745832139063912
429 2582892447449105799
430 2729791486744526125
431 2884865596571102128
432 3048559972224174230
433 3221343535101393902
434 3403710170225628471
435 3596180026944349616
436 3799300885965977760
437 4013649596042233808
438 4239833583772624765
439 4478492440171264764
440 4730299587820620787
441 4995964032615369758
442 5276232204302149663
443 5571889890218833256
444 5883764266856880582
445 6212726034088486987
446 6559691657142638329
447 6925625721651870980
448 7311543407357693378
449 7718513086325391287
450 8147659051808221700
451 8600164384190371928
452 9077273960756517288
453 9580297616351292383
454 10110613462341452965
455 10669671371641659552
456 11258996637945001211
457 11880193817682345262
458 12534950763652678956
459 13225042859684331136
460 13952337466145474327
461 14718798586582581528
462 15526491766264705193
463 16377589233917224592
464 17274375298477121832
465 18219252013253700863
466 19214745120479772017
467 20263510289845571980
468 21368339665262490443
469 22532168734770338400
470 23758083539220619582
471 25049328236095800925
472 26409313035611930082
473 27841622527051552419
474 29350024414131899504
475 30938478679090420944
476 32611147196110746974
477 34372403815669437644
478 36226844942414193905
479 38179300630235177509
480 40234846219314177712
481 42398814541088296137
482 44676808718295620361
483 47074715588527582802
484 49598719781059613712
485 52255318478110660613
486 55051336893150564880
487 57993944500384635546
488 61090672051152877897
489 64349429414629628641
490 67778524281968298616
491 71386681774842246219
492 75183065001250556272
493 79177296603434603335
494 83379481344850102304
495 87800229785296763839
496 92450683095602239860
497 97342539065619415142
498 102488079361797805692
499 107900198093173932325
500 113592431747361765216
501 119578990560943637389
502 125874791391652030320
503 132495492162817511200
504 139457527953817791922
505 146778148813635318753
506 154475459378193998879
507 162568460375824297928
508 171077092109097824836
509 180022280005294937772
510 189425982332011300344
511 199311240178804234982
512 209702229810414561016
513 220624317501892417152
514 232104116971015669221
515 244169549528626917302
516 256849907073030038625
517 270175918060306589873
518 284179816588434304768
519 298895414739325498208
520 314358178329474736560
521 330605306226715102272
522 347675813397743185288
523 365610617858505811520
524 384452631707356680632
525 404246856428992539394
526 425040482665703315329
527 446882994661313407753
528 469826279592478428277
529 493924742011648599351
530 519235423636140866101
531 545818128728273327831
532 573735555322561683225
533 603053432567444701636
534 633840664461036575634
535 666169480272908267088
536 700115591957017704747
537 735758358874529512167
538 773180960159561852117
539 812470575075749767262
540 853718571727081702904
541 897020704502653325059
542 942477320651948793296
543 990193576404886970539
544 1040279663069353669955
545 1092851043558152133255
546 1148028699817424295016
547 1205939391649524948805
548 1266715927445249541602
549 1330497447363100257300
550 1397429719517144694064
551 1467665449759840936100
552 1541364605672178510816
553 1618694755400512828464
554 1699831422007755941200
555 1784958454035999644888
556 1874268413008437841948
557 1967962978630481784980
558 2066253372483459286068
559 2169360801039151153384
560 2277516918859878823782
561 2390964312886783180382
562 2509957008758609816619
563 2634761000144594122045
564 2765654802118188993424
565 2902930029643292443789
566 3046892002291579939943
567 3197860376358391779266
568 3356169805595693120956
569 3522170631833764736728
570 3696229606818804062696
571 3878730646651415080912
572 4070075620271350432830
573 4270685173496705794421
574 4480999590191425771884
575 4701479692203314631416
576 4932607779786108631607
577 5174888614293462471241
578 5428850445010286932024
579 5695046082067619038400
580 5974054017471536257024
581 6266479596364399890655
582 6572956240728339910557
583 6894146727836288638552
584 7230744525855447779680
585 7583475189111713654091
586 7953097815631781124427
587 8340406569692266272990
588 8746232272222707573288
589 9171444062031658382433
590 9616951130952752578680
591 10083704536140509165546
592 10572699092884311084080
593 11084975351453335894671
594 11621621661635787019675
595 12183776328792534826259
596 12772629865408792164603
597 13389427342297645460299
598 14035470843786804359144
599 14712122031404737103033
600 15420804820775076487840
601 16163008176628812851664
602 16940289031053001136346
603 17754275330312464886043
604 18606669215808058187288
605 19499250344971406658280
606 20433879358142457449945
607 21412501497732681003640
608 22437150386244170232120
609 23509951969993198131520
610 24633128635676935883586
611 25809003507224020182949
612 27040004930684397849961
613 28328671155241497325310
614 29677655218771214009560
615 31089730046727548873060
616 32567793773505085617348
617 34114875295813933672877
618 35734140068004380208343
619 37428896149696513214983
620 39202600516505613165866
621 41058865645107365845929
622 43001466384359202595576
623 45034347124685540959948
624 47161629278446664763533
625 49387619084543808721120
626 51716815751068032624070
627 54153919950378025207136
628 56703842681593591483777
629 59371714516117613001552
630 62162895242451269452353
631 65082983927245805716068
632 68137829410240724677080
633 71333541251473506262827
634 74676501149911619638172
635 78173374853454267653383
636 81831124581080834936442
637 85657021978786161186496
638 89658661631841465410644
639 93843975156854765741920
640 98221245898078162123228
641 102799124253422190621128
642 107586643656691857882223
643 112593237243655970030687
644 117828755230703327425792
645 123303483036027333628496
646 129028160174517202851781
647 135013999958820391696365
648 141272710040379841745022
649 147816513825642520223048
650 154658172804085436470895
651 161811009826213257492534
652 169288933371251039403451
653 177106462845888006986811
654 185278754957127049388391
655 193821631204061554070647
656 202751606535239847011880
657 212085919220189818411078
658 221842561985666165459584
659 232040314469252198571025
660 242698777045101355930962
661 253838406078842959621824
662 265480550671006569352196
663 277647490950742169988108
664 290362477984134084497199
665 303649775364027755392452
666 317534702551015299698936
667 332043680038061294357684
668 347204276414199789417205
669 363045257405800524583649
670 379596636977092498927803
671 396889730574950124243211
672 414957210606397199455104
673 433833164240871135825680
674 453553153633020620721220
675 474154278665688728565732
676 495675242316767415778192
677 518156418757803210631760
678 541639924296595117444712
679 566169691280559794779057
680 591791545082353783770784
681 618553284294143777965975
682 646504764262012275885231
683 675697984097283707394217
684 706187177307064358580640
685 738028906192015196070063
686 771282160165329669786480
687 806008458153076248106976
688 842271955242498416719543
689 880139553751551217573976
690 919681018899904301784056
691 960969099268865943843250
692 1004079652245192423349889
693 1049091774651552225191525
694 1096087938774527684435742
695 1145154134009468338974967
696 1196380014350274139868288
697 1249859051961294297870656
698 1305688697077993614067826
699 1363970544492874899162048
700 1424810506893369595318972
701 1488318995329032153893875
702 1554611107096414108061821
703 1623806821341465697539720
704 1696031202691234511824352
705 1771414613239017483541248
706 1850092933219994492165984
707 1932207790727745577314896
708 2017906800835950327052087
709 2107343814504005860812413
710 2200679177660301416341530
711 2298080000872472596098284
712 2399720440030151273722913
713 2505781988482549221276140
714 2616453781090690668641474
715 2731932910672264552236172
716 2852424757335928915778640
717 2978143331221492708284110
718 3109311629182754268017000
719 3246162005970917888636665
720 3388936560498472155560872
721 3537887537786225569025732
722 3693277747219890690054740
723 3855380997767219062198983
724 4024482550832252770250192
725 4200879591449808474941160
726 4384881718550885842935512
727 4576811455058331368474232
728 4777004778601833176465227
729 4985811673672212004205884
730 5203596706067054279101152
731 5430739620513047517076550
732 5667635962384975322515504
733 5914697724477255363877157
734 6172354019821211462495052
735 6441051781580009942485734
736 6721256491093417643946553
737 7013452935186307804333166
738 7318145993898211199500360
739 7635861459836241483189572
740 7967146890400480726271479
741 8312572494179455852814176
742 8672732052863739481311614
743 9048243880078036383029748
744 9439751818586444648889176
745 9847926277381981216515952
746 10273465310230015301925205
747 10717095737296038210808006
748 11179574311551301136225765
749 11661688931715357400441494
750 12164259903562545326318513
751 12688141251490033073041147
752 13234222082318317165360647
753 13803428003371119143770064
754 14396722596960567554899804
755 15015108953485489686566184
756 15659631265435684290905292
757 16331376484683315956472389
758 17031476045534187315501240
759 17761107656106727971618928
760 18521497160705222189162770
761 19313920475956211070813880
762 20139705603583291745374958
763 21000234722805836655393040
764 21896946365461623202605354
765 22831337677072148596603769
766 23804966767192671535205544
767 24819455152516933331515296
768 25876490296339242622295608
769 26977828248114334859333592
770 28125296386998329418941120
771 29320796273402391024375048
772 30566306612744561926087945
773 31863886335744868467429299
774 33215677799774438281485312
775 34623910115941209936916600
776 36090902606773109078570120
777 37619068399544537231640264
778 39210918160483923114429352
779 40869063975299171977640951
780 42596223381664385589618027
781 44395223559525484086489802
782 46269005685304629842185546
783 48220629456313922369785385
784 50253277791928012902735846
785 52370261718313388603549663
786 54575025443769432176054857
787 56871151632003308005396801
788 59262366880937617655554480
789 61752547414936964798771053
790 64345724998637456283579440
791 67046093080872127587577344
792 69858013177505728416628856
793 72786021502324652836079528
794 75834835855472488705664843
795 79009362779279138421589608
796 82314704991702200832622291
797 85756169107983780315353824
798 89339273661524610787353550
799 93069757435390863896943052
800 96953588116297795662209248
801 100996971283359025469933080
802 105206359744351320134336928
803 109588463232722864851489680
804 114150258479068768435598199
805 118898999671311608038259996
806 123842229318357839665631284
807 128987789532553566825760635
808 134343833746836191437056818
809 139918838883072599847665624
810 145721617988690534542293580
811 151761333359348454802010267
812 158047510166051324699318686
813 164590050605806226771921064
814 171399248595623373112178291
815 178485805030405875889306036
816 185860843626036498181617973
817 193535927369762504159925213
818 201523075600801684975582036
819 209834781744944693499763280
820 218484031727812072118087881
821 227484323092339918590087972
822 236849684847017178020705048
823 246594698072381272269709240
824 256734517314298437943223183
825 267284892793612024215658376
826 278262193462837450273817166
827 289683430941717915360816280
828 301566284364631735974714977
829 313929126174061832153508819
830 326791048895601944710991159
831 340171892931284220696219408
832 354092275409370514546828416
833 368573620130156813974634146
834 383638188648798389396003190
835 399309112537674404346263835
836 415610426872376715145552708
837 432567104987030381496595099
838 450205094546335046922833424
839 468551354983458919010845664
840 487633896354722769903135390
841 507481819663882429436975665
842 528125358710756997623888002
843 549595923520958861250395096
844 571926145415563070979149643
845 595149923781710293285576048
846 619302474607372082827356785
847 644420380845822384471507516
848 670541644677757847618549952
849 697705741741494673412016990
850 725953677404244402006809408
851 755328045150138447311527864
852 785873087163434602022896424
853 817634757188201559341079939
854 850660785748743264491483045
855 885000747818097252150060559
856 920706133025123832969689576
857 957830418493999954481893446
858 996429144413346833105345643
859 1036559992435758204680506045
860 1078282867012160611325971264
861 1121659979769232996615187072
862 1166755937042044668876647344
863 1213637830678143193774532445
864 1262375332233541968497551003
865 1313040790685426232096812664
866 1365709333790921406268651486
867 1420458973225954419912391877
868 1477370713643092753768263684
869 1536528665792273216749868991
870 1598020163853539037608805684
871 1661935887136296009952337501
872 1728369986305182698311894608
873 1797420214298432824915500554
874 1869188062110596906109798884
875 1943778899617692194090008725
876 2021302121629272487842921612
877 2101871299358560116969229104
878 2185604337508669381520946563
879 2272623637180082200079128226
880 2363056264811921249673725255
881 2457034127377212303231410029
882 2554694154060244953683596290
883 2656178484652338909903821335
884 2761634664910811369451826357
885 2871215849134729728033666349
886 2985081010220133575992446262
887 3103395157466831376352040036
888 3226329562418631648034352848
889 3354061993028967470535296930
890 3486776956454328696056941973
891 3624665950788740787095763672
892 3767927726063735546274196496
893 3916768554849860419476082456
894 4071402512807783280025028048
895 4232051769549482817228201098
896 4398946890182885559154135510
897 4572327147926634318410870331
898 4752440848195465188821784000
899 4939545664570947355608248192
900 5133908987087118729105412483
901 5335808283275848119072129151
902 5545531472432589315800405635
903 5763377313579582584307605544
904 5989655807620523942041772102
905 6224688614198282013313937112
906 6468809483785416796925079067
907 6722364705556065561138324900
908 6985713571607230275169421383
909 7259228858117651178576833540
910 7543297324053305786232035986
911 7838320228050156074395890344
912 8144713864127103919591146130
913 8462910116905231994552672965
914 8793357037033331123267473060
915 9136519437544473274895174121
916 9492879511894010649083201414
917 9862937474455895297960873832
918 10247212224281651131541109540
919 10646242032954722635162655200
920 11060585257402304988248870596
921 11490821078557162361549031869
922 11937550266793400043121386109
923 12401395975092707876474641328
924 12883004560931274749022676040
925 13383046437912425211368810574
926 13902216958206089767787702429
927 14441237326893531271898476692
928 15000855549354353968318481560
929 15581847412872763188964524565
930 16185017503681368246412121192
931 16811200260703575844942148564
932 17461261067299855182494795067
933 18136097382368919247298055424
934 18836639912202211795267477125
935 19563853824539069976751852285
936 20318740006320604296229687719
937 21102336366692758069723164404
938 21915719186863237324947463180
939 22760004518473100624335323549
940 23636349632201830178856449573
941 24545954518384736505233802769
942 25490063441483646685032437344
943 26469966550316061134252065189
944 27487001546014408230338233525
945 28542555409755755060618377880
946 29638066192373423434636256048
947 30775024868035493123383225265
948 31954977254251231790928459664
949 33179526000545158689802549128
950 34450332648219815252747067288
951 35769119763712471443576187706
952 37137673148138036478516883408
953 38557844125700463692325347120
954 40031551913748042635461883463
955 41560786077344260951286863840
956 43147609071325501744833702036
957 44794158872919830051925191655
958 46502651708107629478283515669
959 48275384875014995642789200192
960 50114739667744699307042541076
961 52023184404167325561332509969
962 54003277561317007015074365712
963 56057671022162133699653842800
964 58189113437651680015443499328
965 60400453708072483740982330255
966 62694644587892092956738021250
967 65074746418405817640645053833
968 67543930992655542785312305625
969 70105485557241843443021126334
970 72762816955810158951829194376
971 75519455919156409053710847254
972 78379061507067649914595314072
973 81345425707189360304551551937
974 84422478196392910787611172356
975 87614291270304901365249441723
976 90925084946854561989509856907
977 94359232249896508758179614112
978 97921264679174056620859405282
979 101615877873103234393523144120
980 105447937471079864734258600128
981 109422485182241803017054707639
982 113544745067855925413387211656
983 117820130044744976713896114341
984 122254248617423199897990319784
985 126852911846872048250958684968
986 131622140564158512190670206432
987 136568172837378971384704787374
988 141697471700701312510095807706
989 147016733154577648256378107485
990 152532894446509658468531114614
991 158253142642068684740633581707
992 164184923496203591484619535719
993 170335950635211416883750578512
994 176714215060099345424588356862
995 183327994982431921026588357304
996 190185866004135079918578919056
997 197296711653118921834435186016
998 204669734286984576729363653488
999 212314466377497495525492092544
1000 220240782188940445173821826940