0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 15
8 22
9 30
10 42
11 56
12 76
13 100
14 133
15 172
16 225
17 288
18 371
19 470
20 598
21 751
22 945
23 1177
24 1468
25 1815
26 2245
27 2757
28 3386
29 4133
30 5043
31 6121
32 7425
33 8966
34 10818
35 13001
36 15610
37 18677
38 22324
39 26600
40 31662
41 37582
42 44560
43 52701
44 62261
45 73387
46 86406
47 101522
48 119153
49 139578
50 163328
51 190782
52 222615
53 259335
54 301799
55 350682
56 407072
57 471858
58 546417
59 631915
60 730093
61 842469
62 971239
63 1118371
64 1286632
65 1478558
66 1697628
67 1947097
68 2231334
69 2554498
70 2922063
71 3339324
72 3813130
73 4350197
74 4959076
75 5648258
76 6428404
77 7310212
78 8306947
79 9432051
80 10702003
81 12133641
82 13747398
83 15564314
84 17609685
85 19909728
86 22495705
87 25400207
88 28661808
89 32320926
90 36425073
91 41024266
92 46176934
93 51944837
94 58399713
95 65617664
96 73686636
97 82700214
98 92766042
99 103998989
100 116530612
101 130501640
102 146072610
103 163415629
104 182726318
105 204214787
106 228119058
107 254695212
108 284232460
109 317042399
110 353475942
111 393911646
112 438774715
113 488524345
114 543675064
115 604783059
116 672470135
117 747408974
118 830350050
119 922105800
120 1023580848
121 1135755068
122 1259717533
123 1396648486
124 1547857467
125 1714764191
126 1898941402
127 2102094704
128 2326110734
129 2573035996
130 2845131039
131 3144848425
132 3474893657
133 3838202418
134 4238009131
135 4677823684
136 5161508604
137 5693255507
138 6277672029
139 6919758361
140 7625005187
141 8399370728
142 9249391152
143 10182158689
144 11205446141
145 12327686718
146 13558114552
147 14906747094
148 16384543750
149 18003391828
150 19776285740
151 21717317751
152 23841880496
153 26166663981
154 28709884590
155 31491290126
156 34532418901
157 37856614888
158 41489321029
159 45458107038
160 49793001579
161 54526535681
162 59694119147
163 65334103148
164 71488206922
165 78201603669
166 85523404545
167 93506772769
168 102209472830
169 111694018515
170 122028296418
171 133285754670
172 145546111046
173 158895590249
174 173427728448
175 189243668332
176 206453073539
177 225174492145
178 245536396398
179 267677627148
180 291748576387
181 317911727081
182 346342998566
183 377232398635
184 410785554600
185 447224497052
186 486789402709
187 529739532432
188 576355215545
189 626938968118
190 681817752696
191 741344307014
192 805899717732
193 875894994253
194 951774000577
195 1034015314277
196 1123135566666
197 1219691632923
198 1324284437874
199 1437561530300
200 1560221419468
201 1693016594483
202 1836758465865
203 1992320899945
204 2160645849972
205 2342747485716
206 2539718610439
207 2752735477726
208 2983065103814
209 3232070876947
210 3501220889727
211 3792094461721
212 4106391633486
213 4445940740355
214 4812709229352
215 5208812441969
216 5636525937112
217 6098295662980
218 6596751994276
219 7134721499022
220 7715242926387
221 8341580803131
222 9017243640634
223 9745999628739
224 10531897366725
225 11379283959485
226 12292828618506
227 13277543507876
228 14338810607660
229 15482405705113
230 16714528965633
231 18041832519220
232 19471455243534
233 21011054457096
234 22668845486473
235 24453638047698
236 26374881245530
237 28442705303335
238 30667972728474
239 33062326140481
240 35638246433449
241 38409107553168
242 41389242597134
243 44594006505717
244 48039851163854
245 51744397099986
246 55726518793287
247 60006426619988
248 64605763727048
249 69547699629605
250 74857040189583
251 80560334453796
252 86685999475605
253 93264442192059
254 100328201052232
255 107912084967828
256 116053333965257
257 124791777509578
258 134170016683204
259 144233604482754
260 155031252348365
261 166615035369887
262 179040626352726
263 192367529249582
264 206659344355254
265 221984033706756
266 238414221457268
267 256027495468158
268 274906747426023
269 295140515389929
270 316823368793475
271 340056297318152
272 364947146570952
273 391611059336547
274 420170968450089
275 450758097247622
276 483512516971501
277 518583714098532
278 556131220533931
279 596325256463102
280 639347442619632
281 685391528390222
282 734664196597872
283 787385887805881
284 843791709352248
285 904132368161759
286 968675197220031
287 1037705210731841
288 1111526262849618
289 1190462240728936
290 1274858372149062
291 1365082573936513
292 1461526927155658
293 1564609200520363
294 1674774514117998
295 1792497059836575
296 1918281977142308
297 2052667295243129
298 2196226047301602
299 2349568462070918
300 2513344346124756
301 2688245556073508
302 2875008681972061
303 3074417834995667
304 3287307669186888
305 3514566523685747
306 3757139824449114
307 4016033624842310
308 4292318433959266
309 4587133204646789
310 4901689640634525
311 5237276686944469
312 5595265374270200
313 5977113873290196
314 6384372941692669
315 6818691611242709
316 7281823310611922
317 7775632262230202
318 8302100362742106
319 8863334375803317
320 9461573661647014
321 10099198262166588
322 10778737581850713
323 11502879472849104
324 12274479981546574
325 13096573553965889
326 13972383975640504
327 14905335831817398
328 15899066783205714
329 16957440431161135
330 18084560088507279
331 19284783217394883
332 20562736872900293
333 21923333900752317
334 23371790252020638
335 24913643149615286
336 26554770495315824
337 28301411238113521
338 30160187120360520
339 32138125507917748
340 34242683750603262
341 36481774764025408
342 38863794311100976
343 41397649658729062
344 44092790122277900
345 46959239157253767
346 50007628547711433
347 53249234334205723
348 56696015070487991
349 60360652034741238
350 64256592027162124
351 68398092362276744
352 72800268733594134
353 77479145541224615
354 82451709409310625
355 87735965465837592
356 93350997164637378
357 99317029203861363
358 105655494377723796
359 112389103897348320
360 119541922078851156
361 127139444915993004
362 135208683501565900
363 143778251796396952
364 152878459781248319
365 162541411472226344
366 172801108911592936
367 183693561596648907
368 195256902541146781
369 207531510414459454
370 220560139041972636
371 234388053695177964
372 249063175550923141
373 264636233732468170
374 281160926415357318
375 298694090396102363
376 317295880718437056
377 337029959741953063
378 357963697368519688
379 380168381799908498
380 403719442672308200
381 428696685931936488
382 455184542438181297
383 483272329651858465
384 513054528547119329
385 544631075101050675
386 578107668663934393
387 613596096564272797
388 651214577429371226
389 691088122579863737
390 733348918171349688
391 778136727450697758
392 825599316008370744
393 875892899409153418
394 929182616308013418
395 985643026454804081
396 1045458636938605325
397 1108824456104193485
398 1175946578755835800
399 1247042802118195808
400 1322343276456061796
401 1402091189869683400
402 1486543491478018081
403 1575971652564691251
404 1670662470235760783
405 1770918913234602748
406 1877061014828330190
407 1989426812495699560
408 2108373339727304856
409 2234277669768600547
410 2367538017046787343
411 2508574896230653253
412 2657832345131506083
413 2815779211533054050
414 2982910510665655419
415 3159748853574252126
416 3346845953646484134
417 3544784211737213447
418 3754178387754775092
419 3975677359360602505
420 4209965976298414664
421 4457767011251923743
422 4719843216454886131
423 4996999487235395207
424 5290085142487779912
425 5599996323576718275
426 5927678522504007264
427 6274129241209645613
428 6640400793748421232
429 7027603253630102818
430 7436907559055569263
431 7869548778808387464
432 8326829552613032117
433 8810123709251800433
434 9320880077426215658
435 9860626493255429967
436 10430974020676511710
437 11033621389314995513
438 11670359667483739378
439 12343077175637993559
440 13053764659462399344
441 13804520728770111138
442 14597557583043380940
443 15435207030750859568
444 16319926825072997120
445 17254307324239666263
446 18241078501075507333
447 19283117311151924536
448 20383455446282317200
449 21545287484093580546
450 22771979462744805584
451 24067077893014297020
452 25434319239371225470
453 26877639883911253609
454 28401186607548327873
455 30009327604188070327
456 31706664065302552976
457 33498042352685366946
458 35388566800109283253
459 37383613163947689948
460 39488842767084870018
461 41710217358710904923
462 44054014738256978997
463 46526845168879610401
464 49135668633038462195
465 51887812958695489889
466 54790992873360160218
467 57853330017965300916
468 61083373982905653835
469 64490124402052187038
470 68083054172648228598
471 71872133841138060464
472 75867857228917673100
473 80081268342746008606
474 84523989650446653976
475 89208251771821043286
476 94146924672651278322
477 99353550417440664447
478 104842377576682099782
479 110628397350627709502
480 116727381513986870097
481 123155922250508686760
482 129931473991304774761
483 137072397333573167057
484 144598005163872404202
485 152528611071104348162
486 160885580184591966083
487 169691382531778852676
488 178969649063204624276
489 188745230449606583472
490 199044258812195022918
491 209894212502324459107
492 221323984106229992857
493 233363951803572846624
494 246046054271427374732
495 259403869276236314949
496 273472696162793839586
497 288289642397948357094
498 303893714397110134008
499 320325912807936141817
500 337629332500047173705
501 355849267453490558062
502 375033320817477452640
503 395231520352268078388
504 416496439550485683416
505 438883324672885107576
506 462450228021876078114
507 487258147712161456098
508 513371174291284189744
509 540856644496166246173
510 569785302530626626558
511 600231469179299359998
512 632273219178077357950
513 665992567188701873043
514 701475662835975506190
515 738812995190547800078
516 778099607197608596649
517 819435320473191825276
518 862924971014105430110
519 908678656285688749547
520 956811994283263478286
521 1007446395078073135170
522 1060709345497975148634
523 1116734707504750782908
524 1175663030977653949678
525 1237641881521027531520
526 1302826184070372324873
527 1371378582976007825262
528 1443469819409369251532
529 1519279126838233020033
530 1598994645493001196798
531 1682813856643872362146
532 1770944037695121239824
533 1863602738996820503069
534 1961018283471954956118
535 2063430290047379618196
536 2171090222086621975112
537 2284261961909409173646
538 2403222412705039758186
539 2528262129029982677586
540 2659685977315824852037
541 2797813827693354416339
542 2942981278688669970064
543 3095540416223313517302
544 3255860608615816856010
545 3424329339154660171148
546 3601353078094310383295
547 3787358195795201414097
548 3982791919027520215763
549 4188123332324553541153
550 4403844426588814514820
551 4630471197016896677236
552 4868544792746137918152
553 5118632720485917509585
554 5381330104754507719357
555 5657261007199366671032
556 5947079807859204674727
557 6251472651080599947279
558 6571158959206213926715
559 6906893017003879182982
560 7259465630235522348362
561 7629705861615238733361
562 8018482847862639098529
563 8426707701406484310295
564 8855335500779362372445
565 9305367373592071669104
566 9777852676492999038211
567 10273891276365247866559
568 10794635937563873598000
569 11341294819843228548779
570 11915134092209239901700
571 12517480667779973317945
572 13149725065360281131503
573 13813324403286547186139
574 14509805531760191005323
575 15240768309741395776996
576 16007889033180147034578
577 16812924021218077841567
578 17657713367746180604426
579 18544184865564605600018
580 19474358111191460648673
581 20450348798234719266484
582 21474373208094591791356
583 22548752906638373027406
584 23675919656399255425076
585 24858420553734321355031
586 26098923401346579480258
587 27400222326470481527816
588 28765243656054423971790
589 30197052060181137955622
590 31698856976069912293101
591 33274019324927019712122
592 34926058535087627992998
593 36658659884832367454916
594 38475682179517770865068
595 40381165777619855223900
596 42379340981630950670206
597 44474636809733083435275
598 46671690165602930293221
599 48975355423713008520313
600 51390714449022892730572
601 53923087069993978724832
602 56578042025494894999931
603 59361408406238482556186
604 62279287613136866299466
605 65338065855073467294556
606 68544427210456573118856
607 71905367277074772466597
608 75428207436769255612296
609 79120609761642373477864
610 82990592590654900344183
611 87046546805723403251833
612 91297252838710678967388
613 95751898441022181384182
614 100420097249962349850172
615 105311908186392775115637
616 110437855720846317462690
617 115808951045715120711250
618 121436714193926495984101
619 127333197145068757965357
620 133511007962922613127369
621 139983336008995367904364
622 146763978279860910608502
623 153867366916853802078348
624 161308597940099477878305
625 169103461259722761245975
626 177268472020755567770137
627 185820903339251828427454
628 194778820491059699839215
629 204161116615828480756062
630 213987550003052820551811
631 224278783028238832914260
632 235056422811806312071448
633 246343063674793748777150
634 258162331470289786315233
635 270538929871154959767584
636 283498688699806583198592
637 297068614387686344403903
638 311276942657617903594743
639 326153193524335458927000
640 341728228714459398594702
641 358034311609518111286313
642 375105169822048538506704
643 392976060517404593240185
644 411683838600807775783859
645 431267027892070908363965
646 451765895417838744492996
647 473222528954414649293112
648 495680917962201739634422
649 519187038056372497785549
650 543788939166928169684944
651 569536837545289150747017
652 596483211783737963455804
653 624682903018447649154094
654 654193219496690408405602
655 685074045693704152715187
656 717387956175290542059991
657 751200334407616298004177
658 786579496727075761222230
659 823596821689033822949210
660 862326885026505571916136
661 902847600456404757733369
662 945240366584146924460437
663 989590220164639511731008
664 1035985995991832135221956
665 1084520493696978268939630
666 1135290651750963761841706
667 1188397728974833272620934
668 1243947493878995290136206
669 1302050422161231388952026
670 1362821902711218813147633
671 1426382452479867559401013
672 1492857940590685829410137
673 1562379822082011231841047
674 1635085381689289911938017
675 1711117988089332171392180
676 1790627359050360910716468
677 1873769837945637610604342
678 1960708682112000838284999
679 2051614363549950080157953
680 2146664882487249329390172
681 2246046094344768513189824
682 2349952050670552744148001
683 2458585354626424989551340
684 2572157531640779678093696
685 2690889415861248924741321
686 2815011553072516441767038
687 2944764620766434844085676
688 3080399866085610932307067
689 3222179562385520821760220
690 3370377485196828743782152
691 3525279408395670660474147
692 3687183621429081091375607
693 3856401468471206558548999
694 4033257910428389585533674
695 4218092110742252967291854
696 4411258045985612778923808
697 4613125142279894873956794
698 4824078938611939837952773
699 5044521778164965846937006
700 5274873528831453510512652
701 5515572334115896563615948
702 5767075395692435500768315
703 6029859788926144369136932
704 6304423312728209824339412
705 6591285375162868648957377
706 6890987916290176177915737
707 7204096369780504162700857
708 7531200664907978448106681
709 7872916270586443241324271
710 8229885283188353022068448
711 8602777559948299574228311
712 8992291899835625936447520
713 9399157273847225848397006
714 9824134106760762416989464
715 10268015612460970194328923
716 10731629185047727332112332
717 11215837848013277582823499
718 11721541763879426668253040
719 12249679806771010626702240
720 12801231200513377139437783
721 13377217224934432660620760
722 13978702993171871151888126
723 14606799302886954159026065
724 15262664564415563486431462
725 15947506808996595266198453
726 16662585780357124913300162
727 17409215113052416953659871
728 18188764601108999854212004
729 19002662560647726671775558
730 19852398290325510088645332
731 20739524633573996747320866
732 21665660646787735782219927
733 22632494377765732807067200
734 23641785758898062846237941
735 24695369619753266352063738
736 25795158823924571608301295
737 26943147535170781364958733
738 28141414618105642684140633
739 29392127178882168145652606
740 30697544251553231198967956
741 32060020635998460363053431
742 33482010893560489699149654
743 34966073506759669878259849
744 36514875209728959681187472
745 38131195496255503232604351
746 39817931312609109009576013
747 41578101942602873408735735
748 43414854092647625940279768
749 45331467184848761348560101
750 47331358866534934781399115
751 49418090744918592545895709
752 51595374355955585449141151
753 53867077376807099178432918
754 56237230091702805621143511
755 58710032121367646933222345
756 61289859426600915085416333
757 63981271596989505122355899
758 66789019436196406105198516
759 69718052855690773700204937
760 72773529089280581698473672
761 75960821241268733773352239
762 79285527181586363410299064
763 82753478801754274068195162
764 86370751646097444748343465
765 90143674933175037888292368
766 94078841983006602349726494
767 98183121066256138601084786
768 102463666692201627843711532
769 106927931352945483400770721
770 111583677742038650002584981
771 116438991466369498226271154
772 121502294270941192332595083
773 126782357796894162269307915
774 132288317893962334157852530
775 138029689509343527228735800
776 144016382175860490346417664
777 150258716123144203548145394
778 156767439036536069993077113
779 163553743489329124058021846
780 170629285075007579048734661
781 178006201267141214158637700
782 185697131035710156144680070
783 193715235249712197673823759
784 202074217897109795574198000
785 210788348154336060741151562
786 219872483338876544290432953
787 229342092779698016749336369
788 239213282641692460501136238
789 249502821741658258303446389
790 260228168394844683254171415
791 271407498332546618104405181
792 283059733732855790875221888
793 295204573408250968971620524
794 307862524195452897935955700
795 321054933594670158450011400
796 334804023707238848697225976
797 349132926522493191782990824
798 364065720606724400472456056
799 379627469249063425518656250
800 395844260121297811936352124
801 412743246510766356453860298
802 430352690187815902306426758
803 448702005971605159469716510
804 467821808060559678385143745
805 487743958196262545010396633
806 508501615732276691364313817
807 530129289682068811083023814
808 552662892823122777787652622
809 576139797937213016797290852
810 600598896269948346746892369
811 626080658295803730047362586
812 652627196878236330311977846
813 680282332917830671479492291
814 709091663585053525898111334
815 739102633237807414202807420
816 770364607127883621958515222
817 802928948004303511646164305
818 836849095725745870553557273
819 872180649998446761194337909
820 908981456360486531903173290
821 947311695537891041855026721
822 987233976302845515522640860
823 1028813431969180026601652881
824 1072117820665525854811241000
825 1117217629531777074600468431
826 1164186182990128475172355845
827 1213099755247598857463417148
828 1264037687193011645668276327
829 1317082507857475928637704282
830 1372320060613931933361636918
831 1429839634297861997221063999
832 1489734099438281178951695086
833 1552100049795159673425683559
834 1617037949406971165232838465
835 1684652285359637910815901243
836 1755051726496253617385767636
837 1828349288295120923972314001
838 1904662504152361186792270998
839 1984113603314132529569001266
840 2066829695712869052212466402
841 2152942963971401513113100654
842 2242590862848901519514991181
843 2335916326412757923222056751
844 2433067983231332949053471331
845 2534200379893485249211640961
846 2639474213172399174690316794
847 2749056571163029936778323940
848 2863121183734999963384581084
849 2981848682655444803205278534
850 3105426871749770767493447760
851 3234051007481908707103388894
852 3367924090350119758589828112
853 3507257167509061624861082976
854 3652269647044377448619323727
855 3803189624341829178647439008
856 3960254221009712762728481244
857 4123709936830241637430175966
858 4293813015233548061140131255
859 4470829822806178453299278281
860 4655037243365261557436400071
861 4846723087149126960070416830
862 5046186515695892348536486152
863 5253738483002610215063366856
864 5469702193579849540056328428
865 5694413578039242822130649268
866 5928221786875471073996212864
867 6171489703128513566729453889
868 6424594474637710455400791263
869 6687928066625365214617127125
870 6961897835375244743786433387
871 7246927123799472824472662451
872 7543455879716993043888259796
873 7851941297697018283872809728
874 8172858485352763837015733568
875 8506701155003259931486777150
876 8853982341655279800049652780
877 9215235148292341635207421162
878 9591013519494515980437005701
879 9981893044450293528811118572
880 10388471790461259251236512909
881 10811371168080633969485862300
882 11251236829069151380807842798
883 11708739598395049802445952982
884 12184576441550493187750052148
885 12679471468503262308605487507
886 13194176975651448388819988073
887 13729474527198857670340904245
888 14286176077421326950244210088
889 14865125135347827827201542980
890 15467197973436590679211726890
891 16093304881884128319470394437
892 16744391470265534586608115818
893 17421440018266342345318420297
894 18125470877331163070039779371
895 18857543925120809486014438308
896 19618760074739304664178362879
897 20410262840763562316179786661
898 21233239964183334012722706546
899 22088925098435658155988342739
900 22978599558798335007969953808
901 23903594137489230067304012373
902 24865290986904371833443149874
903 25865125573516135201214642428
904 26904588705045263724340722210
905 27985228633615293852079422884
906 29108653237697158634921128288
907 30276532285753511533256661021
908 31490599784598764187637032413
909 32752656415600050380708868617
910 34064572061958541468147927986
911 35428288430427749810225894954
912 36845821770947987567522884960
913 38319265697801928198860737611
914 39850794116027664137240391025
915 41442664256960619512093154623
916 43097219826916678074938498247
917 44816894273173697710615138379
918 46604214171559824480869994630
919 48461802740112383389503031664
920 50392383483433338461899439376
921 52398783972533989210034388048
922 54483939765135545174432151633
923 56650898471571015688765280736
924 58902823971620426650369706419
925 61243000787803160499351488967
926 63674838620851290342656186983
927 66201877053293481765808045142
928 68827790427293574182457798318
929 71556392903108569075905414410
930 74391643704760785646842519624
931 77337652559755537531167452040
932 80398685339922316048590056022
933 83579169910711175882391128689
934 86883702196540430839398709464
935 90317052470063814801688477062
936 93884171873508718897104568628
937 97590199180528805768443084448
938 101440467807318154754352961706
939 105440513082046820965333920973
940 109596079782003388802342777847
941 113913129948165363769584980830
942 118397850987267337548409905259
943 123056664071796258202406060907
944 127896232848717279267652939969
945 132923472468118903319491955645
946 138145558943367101239411805394
947 143569938854771006093735776004
948 149204339409192466631722098765
949 155056778868474297682880604950
950 161135577360022500258021372916
951 167449368083352006359913005747
952 174007108926898858769761770984
953 180818094509909989554217346010
954 187891968664750357390365867690
955 195238737375511825940285593770
956 202868782189374485724383590582
957 210792874117754676848053277802
958 219022188044880669273922723497
959 227568317662062187291984167853
960 236443290946569882850865565232
961 245659586204710700082992247027
962 255230148699381246504955418942
963 265168407883098867806780606466
964 275488295258255798269943074730
965 286204262887110437407600219253
966 297331302574828452112102225125
967 308884965749709764776615151497
968 320881384065592821790836611068
969 333337290752309414119424747460
970 346270042740979308983719779303
971 359697643591878443502648898956
972 373638767253595313911746660040
973 388112782683201681688124708266
974 403139779358214030778508082520
975 418740593712205377262088554980
976 434936836527051622893179613535
977 451750921315956496836878534512
978 469206093732603178122691954564
979 487326462043022580934823146722
980 506137028698057328396735877090
981 525663723045630085900249737363
982 545933435223404881672409692410
983 566974051273853555583104515118
984 588814489525216671059907418212
985 611484738283372137999221347578
986 635015894881205983617855213642
987 659440206133711000810248369808
988 684791110248731409001239546588
989 711103280245017792988238886065
990 738412668931067922756987764475
991 766756555500097994655628340768
992 796173593798427347479847125014
993 826703862326559965547090438673
994 858388916034320576834365692048
995 891271839973543830127848781976
996 925397304874034922640202739761
997 960811624710810860221310313300
998 997562816333006862041069794627
999 1035700661227283747595887980938
1000 1075276769491113651885536040300