0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 41
11 56
12 76
13 100
14 133
15 174
16 227
17 293
18 378
19 482
20 614
21 777
22 980
23 1229
24 1538
25 1913
26 2375
27 2936
28 3619
29 4445
30 5447
31 6650
32 8102
33 9844
34 11929
35 14421
36 17397
37 20934
38 25141
39 30130
40 36035
41 43014
42 51253
43 60952
44 72367
45 85771
46 101488
47 119895
48 141425
49 166561
50 195884
51 230040
52 269772
53 315943
54 369532
55 431650
56 503583
57 586791
58 682923
59 793890
60 921840
61 1069219
62 1238818
63 1433809
64 1657751
65 1914745
66 2209382
67 2546876
68 2933129
69 3374832
70 3879476
71 4455617
72 5112818
73 5861910
74 6715073
75 7686068
76 8790271
77 10045137
78 11470120
79 13087189
80 14920926
81 16999024
82 19352342
83 22015721
84 25027942
85 28432606
86 32278351
87 36619765
88 41517576
89 47039990
90 53262821
91 60270971
92 68158908
93 77032274
94 87008375
95 98218426
96 110808008
97 124939594
98 140793545
99 158570897
100 178494456
101 200812562
102 225800242
103 253763475
104 285041190
105 320010048
106 359086742
107 402734213
108 451464253
109 505844631
110 566502995
111 634134925
112 709508608
113 793475010
114 886973280
115 991042536
116 1106829329
117 1235601136
118 1378755262
119 1537835622
120 1714543210
121 1910755624
122 2128540774
123 2370179491
124 2638181908
125 2935315125
126 3264622639
127 3629456600
128 4033502577
129 4480817010
130 4975856768
131 5523524587
132 6129204181
133 6798813283
134 7538847479
135 8356442001
136 9259423945
137 10256386674
138 11356751746
139 12570855993
140 13910027592
141 15386687691
142 17014440872
143 18808196733
144 20784276999
145 22960558009
146 25356600663
147 27993816927
148 30895624034
149 34087642591
150 37597878904
151 41456957053
152 45698338207
153 50358591967
154 55477655872
155 61099156757
156 67270717162
157 74044331573
158 81476732273
159 89629829296
160 98571142165
161 108374319172
162 119119645776
163 130894652165
164 143794717031
165 157923777538
166 173395039802
167 190331814433
168 208868351373
169 229150816294
170 251338277453
171 275603845646
172 302135832822
173 331139089709
174 362836364126
175 397469862416
176 435302848728
177 476621465796
178 521736608285
179 570986053915
180 624736654924
181 683386822440
182 747369097759
183 817153045890
184 893248260594
185 976207743295
186 1066631411082
187 1165170030021
188 1272529318692
189 1389474523305
190 1516835202952
191 1655510560686
192 1806475018673
193 1970784414523
194 2149582505497
195 2344108165379
196 2555702953974
197 2785819486299
198 3036030234252
199 3308037239242
200 3603682356112
201 3924958517297
202 4274021631011
203 4653203655714
204 5065026409176
205 5512216718658
206 5997722456569
207 6524730084803
208 7096683245639
209 7717303088713
210 8390609808531
211 9120946163052
212 9913002432663
213 10771843614479
214 11702938306952
215 12712190162984
216 13805971295290
217 14991158612758
218 16275172458157
219 17666018561745
220 19172332679869
221 20803429038097
222 22569351870620
223 24480931301153
224 26549842847816
225 28788671848395
226 31210982094008
227 33831390102155
228 36665644233601
229 39730710243767
230 43044862471808
231 46627782331491
232 50500663323863
233 54686324409628
234 59209330874352
235 64096124729542
236 69375163795794
237 75077071614740
238 81234797373500
239 87883788212172
240 95062173016533
241 102810960329504
242 111174249520483
243 120199457994746
244 129937563651860
245 140443365664951
246 151775762723841
247 163998052156642
248 177178249147032
249 191389429674184
250 206710096510281
251 223224572285695
252 241023418921502
253 260203887886598
254 280870400714157
255 303135064539444
256 327118222282864
257 352949042749019
258 380766150287359
259 410718299875906
260 442965097501035
261 477677772126994
262 515039999429308
263 555248784266952
264 598515402181783
265 645066407686456
266 695144709998144
267 749010724592527
268 806943601701870
269 869242541049803
270 936228194209609
271 1008244164936892
272 1085658609437174
273 1168865947793597
274 1258288689223088
275 1354379383633733
276 1457622702644310
277 1568537663971922
278 1687680003224171
279 1815644708247836
280 1953068721131109
281 2100633824713178
282 2259069719542029
283 2429157310084586
284 2611732207449986
285 2807688469199308
286 3017982585073825
287 3243637731553928
288 3485748305446104
289 3745484762076722
290 4024098770254092
291 4322928712091618
292 4643405542158092
293 4987059037275222
294 5355524453557209
295 5750549625684301
296 6174002527893853
297 6627879335242960
298 7114313007985486
299 7635582442089459
300 8194122211974457
301 8792532953565987
302 9433592417961274
303 10120267248848403
304 10855725518837120
305 11643350084045289
306 12486752796945391
307 13389789643838184
308 14356576853059535
309 15391508047419010
310 16499272493983071
311 17684874533321321
312 18953654248479599
313 20311309465543561
314 21763919154837503
315 23317968334694571
316 24980374556872192
317 26758516087552046
318 28660261873433582
319 30694003420402626
320 32868688686853856
321 35193858133346185
322 37679683044964704
323 40337006284792427
324 43177385609960754
325 46213139727510416
326 49457397239445796
327 52924148674184299
328 56628301774085191
329 60585740259557307
330 64813386261103641
331 69329266665998735
332 74152583596375762
333 79303789293450441
334 84804665653383912
335 90678408721965826
336 96949718424544440
337 103644893874823327
338 110791934574874671
339 118420647889278835
340 126562763146236603
341 135252052793736482
342 144524461007519947
343 154418240229595862
344 164974096084630058
345 176235341207917194
346 188248058489178106
347 201061274328716441
348 214727142472197094
349 229301139090962426
350 244842269745166969
351 261413288973359374
352 279080933225544447
353 297916167970637527
354 317994449782611433
355 339396004333921124
356 362206121199905705
357 386515466509622301
358 412420414458248868
359 440023398837632607
360 469433285722437474
361 500765768603864961
362 534143787247128811
363 569697971713241991
364 607567112976599883
365 647898661746754118
366 690849257096731756
367 736585286693738652
368 785283480427700869
369 837131539439645266
370 892328802561274107
371 951086952399945441
372 1013630763318387566
373 1080198893802468816
374 1151044725734450726
375 1226437253350546626
376 1306662024699630318
377 1392022138702676854
378 1482839300960260025
379 1579454941765324297
380 1682231399839886365
381 1791553175647473414
382 1907828258214217178
383 2031489529752797333
384 2162996252479852486
385 2302835642413877889
386 2451524535057359555
387 2609611148294476207
388 2777676947979996520
389 2956338622159797293
390 3146250170030935882
391 3348105112259714986
392 3562638829473184066
393 3790631036291874949
394 4032908398507016299
395 4290347301607218409
396 4563876779129294215
397 4854481609969432656
398 5163205594102832032
399 5491155016877706682
400 5839502312414741995
401 6209489937426649075
402 6602434467187129218
403 7019730926240757983
404 7462857366919614893
405 7933379709670440098
406 8432956859743856145
407 8963346115822929291
408 9526408886786646214
409 10124116733933368923
410 10758557756691169810
411 11431943341073511718
412 12146615290941395664
413 12905053363482018382
414 13709883231216059420
415 14563884894331955618
416 15470001568163735066
417 16431349072252737425
418 17451225748589681068
419 18533122938414411634
420 19680736048245617533
421 20897976237775859201
422 22188982763722680746
423 23558136015874893953
424 25010071283216575187
425 26549693290370165822
426 28182191546435888523
427 29913056550905820075
428 31748096903387243177
429 33693457366720528410
430 35755637935388718296
431 37941513964248822439
432 40258357415191674806
433 42713859282792681112
434 45316153262894186508
435 48073840731851474641
436 50996017107399452409
437 54092299666266615840
438 57372856897251003131
439 60848439473072398349
440 64530412928314013942
441 68430792135818087729
442 72562277678367698933
443 76938294218045233804
444 81573030970621125521
445 86481484398458106713
446 91679503240937252742
447 97183836008150642704
448 103012181069759297507
449 109183239478332739601
450 115716770673313481171
451 122633651219932457100
452 129955936744983496888
453 137706927240362407042
454 145911235913710517494
455 154594861775409341220
456 163785266160518929322
457 173511453395179798244
458 183804055827363610882
459 194695423453877595689
460 206219718387038528003
461 218413014417668400964
462 231313401943805779023
463 244961098549124089295
464 259398565529162610537
465 274670630679536365285
466 290824617675942641667
467 307910482393468378197
468 325980956530011900928
469 345091698918133208098
470 365301454928800286404
471 386672224391957041127
472 409269438480050227570
473 433162146024282259163
474 458423209756795521690
475 485129512998040188734
476 513362177334488308460
477 543206791860518492100
478 574753654586958728220
479 608098026650332937396
480 643340399988504931007
481 680586779183188790842
482 719948978204750237820
483 761544932832988379499
484 805499029566217017336
485 851942451873089119740
486 901013544684230220808
487 952858198067149979207
488 1007630251074940359706
489 1065491916810322350320
490 1126614229798539542784
491 1191177516818787314472
492 1259371892401132191463
493 1331397780257752452754
494 1407466461980485292248
495 1487800654404730647854
496 1572635117109433423245
497 1662217291597759542464
498 1756807973779854160328
499 1856682021461512241476
500 1962129098627201315534
501 2073454458396542792136
502 2190979766626628738592
503 2315043968232284655722
504 2446004198399105267067
505 2584236740973833307492
506 2730138036429780800278
507 2884125741925652100565
508 3046639846100750531245
509 3218143841382234143210
510 3399125956717252839935
511 3590100453788741342681
512 3791608989924624089426
513 4004222051070601564844
514 4228540458362899132490
515 4465196952013698398203
516 4714857856404814798668
517 4978224830479066785502
518 5256036707719926753039
519 5549071430223083199905
520 5858148081584842803937
521 6184129023566407449038
522 6527922141736379388959
523 6890483205551138731847
524 7272818348600264890420
525 7675986675026793507655
526 8101102998426263704218
527 8549340719838964005860
528 9021934851773056588699
529 9520185195537318617380
530 10045459679517490974798
531 10599197866404728742428
532 11182914637775054973621
533 11798204064829951574212
534 12446743474537053221975
535 13130297720861497319199
536 13850723671249503096906
537 14609974919021445716292
538 15410106732849052230328
539 16253281255035444502780
540 17141772960884769822272
541 18077974392045405305352
542 19064402177334318121869
543 20103703355205500296000
544 21198662012710000603429
545 22352206256514130182461
546 23567415532293710015520
547 24847528309611194867824
548 26195950150206929229747
549 27616262178501173639548
550 29112229974008178025663
551 30687812906312732657764
552 32347173934251946974715
553 34094689891986019046811
554 35934962285730175786497
555 37872828626061375193512
556 39913374321907125588938
557 42061945163575191963473
558 44324160423491860529108
559 46705926604688401426566
560 49213451868510393125378
561 51853261174528288255715
562 54632212167200805305629
563 57557511845490726498959
564 60636734053356889204951
565 63877837830852183663449
566 67289186667446903893523
567 70879568701175501240030
568 74658217909275359262252
569 78634836338153923346194
570 82819617422788885966962
571 87223270448040760135371
572 91857046206841999549367
573 96732763912827510585308
574 101862839427693129763925
575 107260314866416651784305
576 112938889646456508184060
577 118912953050161827257252
578 125197618372891190731070
579 131808758732751620898259
580 138763044621442569813985
581 146077983279427156102276
582 153771959982564314170763
583 161864281331426527713731
584 170375220638808989932938
585 179326065515413102601897
586 188739167758372681339849
587 198637995652190321582080
588 209047188796778258972044
589 219992615582658479166533
590 231501433438986137016872
591 243602151985924423561115
592 256324699229035569218758
593 269700490939767083417829
594 283762503372824411658871
595 298545349478236942930131
596 314085358773265109589653
597 330420661046968407843865
598 347591274078281818198402
599 365639195556837058988578
600 384608499404542297883564
601 404545436705105876672602
602 425498541458285288883258
603 447518741385668927050987
604 470659474025287572321098
605 494976808363311648955888
606 520529572262554808562331
607 547379485959481831711533
608 575591301913947745527203
609 605232951308983363117109
610 636375697511633152232352
611 669094296820152037106895
612 703467166837825563570997
613 739576562829301674836942
614 777508762431662789174598
615 817354259109533584032663
616 859207964761368909045591
617 903169421902707105396410
618 949343025871667893032938
619 997838257522332086750528
620 1048769926892928403443050
621 1102258428357982865164416
622 1158430007796831113981358
623 1217417042335165872857438
624 1279358333241669559908289
625 1344399412588280418399124
626 1412692864310343947471396
627 1484398660331826309195132
628 1559684512451005403800809
629 1638726240713625506427079
630 1721708159033503389482182
631 1808823478855027685073007
632 1900274731688006811548059
633 1996274211382916457584797
634 2097044437053893387483568
635 2202818637597841885546443
636 2313841258800890428733312
637 2430368494068186723636257
638 2552668839859786247822871
639 2681023676964203822303662
640 2815727878792209088749734
641 2957090447926688255509594
642 3105435182220028037100873
643 3261101371788541686244650
644 3424444528314125026495322
645 3595837148126645467086237
646 3775669510606718024817211
647 3964350513517555974556225
648 4162308546946704157253764
649 4369992407613723641289208
650 4587872255378516373532894
651 4816440613867017572466505
652 5056213417216679784596681
653 5307731105033590972622939
654 5571559767746466695035147
655 5848292344640207711280436
656 6138549876953494764046986
657 6442982818531084990769226
658 6762272406632378266625690
659 7097132095613527630291099
660 7448309056321198401621895
661 7816585744162138583305261
662 8202781538944354657101771
663 8607754459723006760829351
664 9032402958027520302665620
665 9477667792995983054880473
666 9944533992099062053802682
667 10434032901298574867697636
668 10947244328655918785381158
669 11485298785582956866677384
670 12049379830113151077088728
671 12640726516763892678906268
672 13260635957762614949203693
673 13910466000619576884081723
674 14591638027249722076612792
675 15305639880074959501656552
676 16054028920777169986259024
677 16838435227621449486883193
678 17660564937529191236577185
679 18522203739351846671162188
680 19425220525079269526692806
681 20371571206011730226919022
682 21363302701232723265738368
683 22402557106040898381073785
684 23491576048334618636942241
685 24632705241292140704130533
686 25828399241055074674732338
687 27081226418503005631837039
688 28393874154603865106792409
689 29769154269238258053819336
690 31210008693827469453011629
691 32719515398544771601214291
692 34300894585358991129632535
693 35957515158648600334292581
694 37692901485635017828925783
695 39510740459415915366661219
696 41414888877934367089667747
697 43409381152798282010426293
698 45498437362468058183219651
699 47686471664959489505241607
700 49978101085865076824591432
701 52378154698180811802172764
702 54891683211138759134938731
703 57523968985989207200990197
704 60280536497451448501657373
705 63167163260360319949727130
706 66189891241878269986206335
707 69355038780520941973756702
708 72669213034160000766605318
709 76139322980121301411316156
710 79772592991491579594701402
711 83576577014783860884292933
712 87559173375192977692206730
713 91728640236799290817368843
714 96093611746253347206287352
715 100663114889698240851691105
716 105446587093962471695538998
717 110453894604385732136982655
718 115695351673026088593168111
719 121181740592441228242204234
720 126924332611741821351606536
721 132934909773183539165437980
722 139225787709199106456359704
723 145809839441475069548649774
724 152700520225453219938047809
725 159911893485486134907973523
726 167458657887803845482364505
727 175356175600456741326930618
728 183620501791492522920255730
729 192268415418805069476541368
730 201317451367364875970059813
731 210785933991907227355939964
732 220693012125620230535579886
733 231058695617943497795810502
734 241903893467264735169911167
735 253250453617089318050990953
736 265121204487162597692207915
737 277539998314050076865130689
738 290531756378832607809225018
739 304122516202856659607139607
740 318339480795899811135623554
741 333211070044673592492516108
742 348766974333296454857034912
743 365038210491234047564968892
744 382057180168229484503703025
745 399857730739938398354183513
746 418475218852350236519927853
747 437946576717624446014878913
748 458310381278706472849801156
749 479606926365020387354854845
750 501878297966671650677869662
751 525168452759942164910672778
752 549523300022430216220383255
753 574990787081987958461028136
754 601620988449649386713475315
755 629466198793030716612472218
756 658581029913234239441095316
757 689022511895105206939072982
758 720850198607791521993357133
759 754126277739947911152272332
760 788915685561623211594552125
761 825286226612882211365262373
762 863308698527556556371019291
763 903057022209204315651218462
764 944608377585400406292766300
765 988043345175892969343211727
766 1033446053719960701057712753
767 1080904334118506914127282291
768 1130509879957045775336102097
769 1182358414886789769242484240
770 1236549867152554406491220819
771 1293188551568172846510658452
772 1352383359252580391004764719
773 1414247955452704422859891688
774 1478900985792801896899957571
775 1546466291303943145103514654
776 1617073132601971863421367518
777 1690856423597497541378286761
778 1767956975137324502811829871
779 1848521748993213737622652553
780 1932704122631038082012822336
781 2020664165211252556210533765
782 2112568925290190237628744547
783 2208592730711036505112966875
784 2308917501193463655551122065
785 2413733074151852555219719356
786 2523237544293823514041859819
787 2637637617573476171082317153
788 2757148980097335955185034564
789 2881996682605556453438936498
790 3012415541176473853769975906
791 3148650554829188146692334593
792 3290957340726500236656698831
793 3439602587709304202961388344
794 3594864528923467344901556504
795 3757033434331370315513212875
796 3926412123932676987733314235
797 4103316502552605214887482715
798 4288076117091030728247303614
799 4481034737162227421156527476
800 4682550960092987864753029325
801 4892998841286332598873082875
802 5112768550999069848000576933
803 5342267058624167803792464257
804 5581918845613318785037791636
805 5832166648221272264622968770
806 6093472231301566585271782133
807 6366317194433266231062143951
808 6651203811710293224420718961
809 6948655906579002260386364062
810 7259219763165876249522641560
811 7583465075595692806494460532
812 7921985936861326262521386512
813 8275401868869591361913888141
814 8644358895353304541022413288
815 9029530659408131021512634560
816 9431619587483909282659349412
817 9851358101734100923286659339
818 10289509882703920249621886297
819 10746871184417664509597999607
820 11224272204008918352114361510
821 11722578508123764091305681729
822 12242692518417028243302524223
823 12785555058555063482033460385
824 13352146965235749620809459921
825 13943490765837436749752755992
826 14560652425413605530780395920
827 15204743165859234316568746273
828 15876921360188409646850035979
829 16578394504980758316242879073
830 17310421274176998076892101419
831 18074313657531475682619114839
832 18871439187162181968916581879
833 19703223255776593542133879223
834 20571151530295001146205866375
835 21476772464741950581251707681
836 22421699916431271171609603007
837 23407615869631120224575897149
838 24436273271062775273847191126
839 25509498981760797710888252371
840 26629196850002936165541919527
841 27797350910205993218714291562
842 29016028712879129518811086680
843 30287384790929003061786737878
844 31613664267822045008218505950
845 32997206613328356845756661535
846 34440449552799507257311076487
847 35945933136169234349635532935
848 37516303973112075555685809051
849 39154319641050602712584748051
850 40862853272967616478421055696
851 42644898332255729023629039918
852 44503573582123649132992559537
853 46442128257376585783051817435
854 48463947446697948797356026033
855 50572557693881386550618747619
856 52771632826796638806959829508
857 55065000023220170193152360127
858 57456646123022601028584311522
859 59950724196580076865203866276
860 62551560379666469953987861646
861 65263660985488234419872923389
862 68091719904944438392064014789
863 71040626306631563045049343398
864 74115472648566732209395350092
865 77321563014074755494730360391
866 80664421784774423432828314952
867 84149802664108573326223640033
868 87783698065391292718185397417
869 91572348878894985506894913693
870 95522254633070693839766003414
871 99640184065587846534028148756
872 103933186120495352918869771807
873 108408601388445541201696159621
874 113074074007586779369596991951
875 117937564043420642459414807194
876 123007360366636199917415234829
877 128292094048678390799577029683
878 133800752295580605644956364958
879 139542692941394579350052055129
880 145527659523384673751279834378
881 151765796962019752335221253585
882 158267667869695364664015491854
883 165044269513053114668221705712
884 172107051454734221213927542895
885 179467933901411737462817454897
886 187139326785992115156506048537
887 195134149612963230671955799552
888 203465852096994178064055238991
889 212148435626063641302019415400
890 221196475581610147065369667231
891 230625144549460651483283348582
892 240450236456605518503535109262
893 250688191670249813526437473716
894 261356123096984888207361102337
895 272471843321392418768966026479
896 284053892824917450720548034949
897 296121569327429694261091634266
898 308694958295535533054054560548
899 321794964663409211165077509820
900 335443345813682842825393038238
901 349662745867773676082481804068
902 364476731336936008699111419417
903 379909828187306916567901242301
904 395987560374272279667441332403
905 412736489903615290611443330047
906 430184258479126682626074519662
907 448359630798657343471611791772
908 467292539562982989532260840403
909 487014132264330415809444640957
910 507556819823988953410949246661
911 528954327151102658791883694656
912 551241745697512127212983659739
913 574455588086393434344085233965
914 598633844895429540642269920696
915 623816043678350595723356154452
916 650043310311898228374840381857
917 677358432758609460817276423588
918 705805927339282937223457190567
919 735432107612588394013664729662
920 766285155963014660496311065234
921 798415198002227004015322939624
922 831874379892926630435848934032
923 866716948708479038982553809380
924 902999335945909412964375493575
925 940780244314358132965061330953
926 980120737925753954882937296735
927 1021084336019302667824455858210
928 1063737110356411721503319678800
929 1108147786427883125661008848397
930 1154387848620614950872236971034
931 1202531649496663242207175694765
932 1252656523343338696888351143519
933 1304842904159053837869822181075
934 1359174448245904804947311333000
935 1415738161586475649291166819326
936 1474624532189100930875483600789
937 1535927667592823472134167655601
938 1599745437730547741341974323586
939 1666179623356425187870870918805
940 1735336070251326053993738101835
941 1807324849428363126875885060842
942 1882260423568847445697382448749
943 1960261819927785298638164641431
944 2041452809957081613915954841652
945 2125962095904009054593425684076
946 2213923504652247314115618485728
947 2305476189082906155855965029894
948 2400764837243432118535210373647
949 2499939889623176354075364353292
950 2603157764845684243566417394720
951 2710581094099471110772650196894
952 2822378964641188057294159064708
953 2938727172717673640572542550935
954 3059808486266447487436109879642
955 3185812917767748125220761310528
956 3316938007635267230733654049961
957 3453389118547304555930936714336
958 3595379741135181217968345303516
959 3743131811461423612065961749459
960 3896876040736486562731659734114
961 4056852257739643703846192751314
962 4223309764427157632324284738453
963 4396507705228974910868440732100
964 4576715450553995291644963724751
965 4764212995043465071286826592921
966 4959291371132266802799366588197
967 5162253078498847960194431027499
968 5373412530006276983002030894287
969 5593096514759464631003895953917
970 5821644678926971168120262444097
971 6059410025000065851315190591729
972 6306759430186846091770970998708
973 6564074184665291986980387124058
974 6831750550446161567831022512968
975 7110200341624657953038231531248
976 7399851526828858003389386063609
977 7701148854703020464320429407217
978 8014554503295128979668496580736
979 8340548754250411936418866749860
980 8679630692746158706545118975588
981 9032318934137963609830301629767
982 9399152378323619727129287718807
983 9780690992868300818417353682972
984 10177516625973459209332027031295
985 10590233850412080251882885423227
986 11019470839594621508366286404913
987 11465880276973180419797440895277
988 11930140300036233325918780722608
989 12412955480192728449880745182667
990 12915057839892455296714671294204
991 13437207908379514145974194883222
992 13980195817527435708579931911826
993 14544842439258118327858146636946
994 15132000566102326721219373748847
995 15742556136517102719634220950243
996 16377429506635148107009591745541
997 17037576770183128147006659089298
998 17723991128369990358515778708815
999 18437704311612877703785263654772
1000 19179788055037122920465786859682