-1 1
0 0
1 3
2 3
3 8
4 8
5 16
6 17
7 33
8 35
9 59
10 65
11 105
12 116
13 175
14 198
15 292
16 330
17 466
18 533
19 736
20 842
21 1132
22 1304
23 1725
24 1985
25 2576
26 2974
27 3809
28 4394
29 5555
30 6415
31 8030
32 9261
33 11475
34 13234
35 16264
36 18734
37 22843
38 26296
39 31849
40 36613
41 44058
42 50602
43 60551
44 69452
45 82669
46 94714
47 112205
48 128378
49 151402
50 173015
51 203217
52 231916
53 271355
54 309287
55 360612
56 410474
57 476995
58 542266
59 628217
60 713254
61 823900
62 934256
63 1076269
64 1218884
65 1400538
66 1584192
67 1815913
68 2051524
69 2346189
70 2647470
71 3021196
72 3405137
73 3877781
74 4365598
75 4961867
76 5579732
77 6329966
78 7110370
79 8052106
80 9034996
81 10214213
82 11448926
83 12922225
84 14469190
85 16305689
86 18239186
87 20523588
88 22934304
89 25769757
90 28768675
91 32281048
92 36003214
93 40345330
94 44955342
95 50312985
96 56010527
97 62608636
98 69636163
99 77747217
100 86397972
101 96350945
102 106979742
103 119171855
104 132206614
105 147116138
106 163072914
107 181275551
108 200774990
109 222962066
110 246750360
111 273751684
112 302723866
113 335533327
114 370762360
115 410569693
116 453339232
117 501565885
118 553410620
119 611753805
120 674505211
121 744987788
122 820829866
123 905861196
124 997394056
125 1099839201
126 1210155886
127 1333419361
128 1466193719
129 1614314935
130 1773907130
131 1951675283
132 2143252764
133 2356338104
134 2586020038
135 2841130828
136 3116153874
137 3421216090
138 3750131454
139 4114502626
140 4507402458
141 4942116909
142 5410902228
143 5928961302
144 6487649984
145 7104355390
146 7769445326
147 8502792024
148 9293678740
149 10164806551
150 11104273805
151 12137997426
152 13252781528
153 14478200265
154 15799650936
155 17250861912
156 18815702452
157 20532621165
158 22383835876
159 24413152920
160 26601007895
161 28997289833
162 31580521391
163 34407490899
164 37454672216
165 40786680459
166 44377808514
167 48301543181
168 52529863126
169 57146312147
170 62120430950
171 67547155738
172 73393470634
173 79767217575
174 86632723686
175 94112441619
176 102167955828
177 110938259955
178 120382141126
179 130657308461
180 141719725768
181 153748277510
182 166696127524
183 180766106290
184 195908649990
185 212353667039
186 230049013312
187 249255202036
188 269917733586
189 292331710174
190 316440612160
191 342578616313
192 370687635848
193 401145986100
194 433894625374
195 469361707391
196 507488019992
197 548757986565
198 593113234512
199 641101693726
200 692667088263
201 748429015549
202 808334867906
203 873085091048
204 942632665260
205 1017769232452
206 1098455714234
207 1185586586385
208 1279133548696
209 1380107021207
210 1488492910610
211 1605432321616
212 1730929460328
213 1866272713680
214 2011489481054
215 2168034087468
216 2335962921587
217 2516917242423
218 2710989300866
219 2920030882924
220 3144178190524
221 3385520076320
222 3644246220370
223 3922712355711
224 4221172793914
225 4542283669889
226 4886376989978
227 5256446936581
228 5652918435676
229 6079166025146
230 6535725298570
231 7026398647539
232 7551852937418
233 8116371770395
234 8720777205466
235 9369893938609
236 10064726899640
237 10810709118358
238 11609060415932
239 12465897594976
240 13382692303012
241 14366329785855
242 15418576116215
243 16547179944872
244 17754250773776
245 19048507195498
246 20432458503114
247 21915912674288
248 23501843471128
249 25201282202508
250 27017741303565
251 28963625532717
252 31043070961546
253 33270024073302
254 35649341832094
255 38196700968228
256 40917790469758
257 43830228550091
258 46940663168374
259 50268890583864
260 53822662513376
261 57624218216073
262 61682578242784
263 66022721460727
264 70655125201944
265 75607840008888
266 80893013903048
267 86542140697722
268 92569282254654
269 99009791502921
270 105879920428165
271 113219346239884
272 121046824626600
273 129406877415596
274 138321119763402
275 147839499935767
276 157986895773210
277 168819332535521
278 180365407553824
279 192687950218897
280 205819794393962
281 219831386296678
282 234760381296042
283 250685750436651
284 267650631863220
285 285743535858500
286 305013830546512
287 325560698361640
288 347440581052427
289 370764598352005
290 395597217769990
291 422062908703942
292 450235238225136
293 480253601944835
294 512201877007281
295 546236144522220
296 582451955412166
297 621024039250326
298 662061156399346
299 705758874484122
300 752240891513624
301 801726055216714
302 854354945365176
303 910372412652726
304 969938104312876
305 1033325909530712
306 1100716999340598
307 1172417684593373
308 1248633419063928
309 1329706705337254
310 1415870377558800
311 1507507330142033
312 1604881253652010
313 1708420112761450
314 1818422353685742
315 1935366221253716
316 2059589289056932
317 2191625882866687
318 2331857603321694
319 2480881314195094
320 2639128131912662
321 2807264644614297
322 2985777630922344
323 3175411399405288
324 3376715270621684
325 3590520169014603
326 3817445654916282
327 4058419162229440
328 4314139100523990
329 4585640414935136
330 4873709989979520
331 5179502513193270
332 5503904101463154
333 5848202780214319
334 6213395916809894
335 6600919983006709
336 7011897017808022
337 7447928725986216
338 7910276801211389
339 8400726828309405
340 8920696875843088
341 9472177118403006
342 10056760652197552
343 10676665236904574
344 11333679797325670
345 12030275206609896
346 12768459407284474
347 13550984720099885
348 14380103947596576
349 15258882300410528
350 16189846231085910
351 17176408723830496
352 18221401944058344
353 19328625343916858
354 20501252498563980
355 21743512240059602
356 23058959282802952
357 24452299418928300
358 25927512706505580
359 27489834642566531
360 29143719796333867
361 30894991828582693
362 32748634491410090
363 34711124387434442
364 36788035224686732
365 38986568314254468
366 41312954856004222
367 43775200361859217
368 46380268551927102
369 49137057171800967
370 52053345790521210
371 55139021857912946
372 58402773311692072
373 61855585205234757
374 65507156541177616
375 69369689395708567
376 73454007795512498
377 77773662983352495
378 82340730433036018
379 87170256748149258
380 92275709060325580
381 97673791041692140
382 103379516942527668
383 109411426334742207
384 115786252909507709
385 122524569868792928
386 129645021307527894
387 137170432640535013
388 145121569929616808
389 153523752390939623
390 162400102379070590
391 171778699874082088
392 181685282993078219
393 192150987425903400
394 203204454291998882
395 214880200789376740
396 227210088940288260
397 240232377261386201
398 253982500425277084
399 268502855563214735
400 283832839098951046
401 300019425382920225
402 317106402906936322
403 335145807355530368
404 354186295070738576
405 374285497319173606
406 395497464219559956
407 417886012080679052
408 441511166013872286
409 466443577627828324
410 492749889194913850
411 520508304814205109
412 549792793264965974
413 580689902003984302
414 613281709689083826
415 647663979084358143
416 683927763648955186
417 722179002623355217
418 762518679016998800
419 805063967867779395
420 849926835400574246
421 897236859734913130
422 947118152883689980
423 999713982062305275
424 1055161887522993978
425 1113620242142756229
426 1175241428797191372
427 1240200486110976238
428 1308666199131549422
429 1380831990071520324
430 1456884765394466330
431 1537038222105880360
432 1621499282971340324
433 1710504001485666325
434 1804281404748608880
435 1903092193709730675
436 2007189800183381592
437 2116862093402131794
438 2232389443694471818
439 2354089661838813436
440 2482272847002392416
441 2617289801953153992
442 2759483426891618548
443 2909240871314363287
444 3066941218303056796
445 3233011652833728580
446 3407871162834182586
447 3591991024072615908
448 3785834224788721514
449 3989920589078618704
450 4204761611050912985
451 4430930561938380966
452 4668992397451092764
453 4919579218807702912
454 5183314893146311894
455 5460896265378451677
456 5753012106086905432
457 6060430499697893593
458 6383911707123109586
459 6724302186333767505
460 7082440927991656326
461 7459260597244477351
462 7855686869602390440
463 8272747217787715543
464 8711462742035415596
465 9172965163293474254
466 9658380606805979074
467 10168955403022582887
468 10705931245631849776
469 11270680444393333016
470 11864571838555926430
471 12489116191645125727
472 13145822198279176636
473 13836352759946641513
474 14562370377430588156
475 15325705098993068880
476 16128188541767466116
477 16971834359775336105
478 17858660085534401632
479 18790881025192704232
480 19770719056035288145
481 20800610920011790647
482 21883003053567534222
483 23020575319218489330
484 24216020880967885336
485 25472286486664878884
486 26792336334925584245
487 28179410099089652909
488 29636769659802297842
489 31167976144816055824
490 32776618324904873665
491 34466610032878288927
492 36241898939015956416
493 38106785807875275418
494 40065612282615188096
495 42123103539864007833
496 44284033619835662376
497 46553593148142374095
498 48937030650114189366
499 51440047124422043616
500 54068411675143712622
501 56828384845927138131
502 59726306791676669664
503 62769051414225033913
504 65963585176650079786
505 69317454222624906947
506 72838311809840260632
507 76534440745924807206
508 80414247282799677754
509 84486821362969966357
510 88761394673342075250
511 93247941367419129084
512 97956597824671407937
513 102898306697474509408
514 108084195759941735434
515 113526268324048009648
516 119236738389351678190
517 125228770681499399436
518 131515769130816987924
519 138112170009113565309
520 145032680570079132954
521 152293128997960907685
522 159909649835325235878
523 167899594710700642171
524 176280660958839142492
525 185071867364894964598
526 194292622148025195058
527 203963768248163287786
528 214106586594841573332
529 224743915770351855180
530 235899086221127139150
531 247597119459265139343
532 259863588592788985880
533 272725902577530542272
534 286212088144068628914
535 300352164985198446419
536 315176843840330918754
537 330718998901780201101
538 347012276480750866474
539 364092671340013263931
540 381997040008199417416
541 400764788198878187666
542 420436282460448151288
543 441054656323936339930
544 462664113573080508582
545 485311861277359878920
546 509046297539479099484
547 533919080118199236501
548 559983191056991619252
549 587295150185436384196
550 615912948551727076680
551 645898416714013036167
552 677315018389167119202
553 710230384109025931195
554 744713955956629563254
555 780839697869434606283
556 818683581760383769988
557 858326486503722453251
558 899851515129811368736
559 943347095332086540014
560 988904116779584568554
561 1036619246839115974566
562 1086591876365872639502
563 1138927665246343016859
564 1193735284302997640790
565 1251130206234554205063
566 1311231230503199349186
567 1374164536283260114567
568 1440059976386368592364
569 1509055409931585724881
570 1581292750502704117280
571 1656922597426647306374
572 1736100022445129276296
573 1818989519738430763122
574 1905760514427966533004
575 1996592652814130921688
576 2091671015004079283882
577 2191191768250563331965
578 2295357064917180417241
579 2404381083315434421454
580 2518484591074651952820
581 2637901399482923438774
582 2762872571117264264554
583 2893653315406784337520
584 3030506818096955120574
585 3173711607577122324947
586 3323554982396998323594
587 3480340879842459264939
588 3644382876288720640932
589 3816012591575927724440
590 3995572235467566050460
591 4183423583578573559139
592 4379940041605092915152
593 4585516230901383311002
594 4800559540453284142920
595 5025500362695039180066
596 5260783101409083750952
597 5506877101029819434356
598 5764267076761340205420
599 6033464783442347947556
600 6314998832176000772621
601 6609427147839617971396
602 6917326134411243104704
603 7239303973411022920951
604 7575989097881626275176
605 7928044387457714318828
606 8296154908605778002654
607 8681043065646928276465
608 9083455562379762027376
609 9504179572243937474841
610 9944028873830501071710
611 10403861107484064737240
612 10884563034441791271312
613 11387068951546441801869
614 11912345020840448774558
615 12461408918717276170284
616 13035313179723247609048
617 13635166161428621943602
618 14262114342948944862214
619 14917364692088796086658
620 15602165855678269059864
621 16317832021151905445469
622 17065722932195623000884
623 17847269342892198350746
624 18663951788380722538360
625 19517327736051191117076
626 20409009036922760709094
627 21340690885127632950480
628 22314127871506430006972
629 23331164869811683718302
630 24393711609588140312870
631 25503775615176028518410
632 26663435210280674079844
633 27874874643994780840000
634 29140355434554149909786
635 30462253825257285034764
636 31843030369741079568360
637 33285269869888447444409
638 34791649099527464999104
639 36364979386218299537013
640 38008172364569433193833
641 39724285374221544648073
642 41516485127972108727786
643 43388096109365531623195
644 45342562034509701663552
645 47383497444481120726901
646 49514646833089978049696
647 51739939641860890534939
648 54063446919042986722751
649 56489439938279248801344
650 59022344246850108350070
651 61666802143347765853946
652 64427623965471232241018
653 67309854677130743023153
654 70318722238063296279910
655 73459708566863504093602
656 76738494826245926858220
657 80161037045593865507947
658 83733508146841548521512
659 87462378528316096049103
660 91354354646932492616748
661 95416464884445726511830
662 99655994491927005117204
663 104080577080116014499228
664 108698125721960842500550
665 113516930430642973155625
666 118545585205297626088906
667 123793091883559234673354
668 129268782904415539978466
669 134982431946877733316724
670 140944172172241738319790
671 147164614086818542644554
672 153654759013661255272198
673 160426124645297866500946
674 167490653482213432712094
675 174860846571315516567038
676 182549666635118434928152
677 190570680523354554641051
678 198937956742872164000646
679 207666217183503500060176
680 216770728744140518481262
681 226267464929811504694170
682 236172991254219969465792
683 246504637343101593844537
684 257280375777681852302044
685 268519005379929206780079
686 280240023144887257835708
687 292463819426562045723976
688 305211542589896245328658
689 318505306861892568220242
690 332368049316101820493710
691 346823751202364464621806
692 361897286858063920087816
693 377614659381750339884268
694 394002841046047611769182
695 411090024235603968802765
696 428905452916419971698422
697 447479689817260145438067
698 466844438489273881744682
699 487032827772423445136793
700 508079223957586730358618
701 530019533645947818264717
702 552891005503286568354934
703 576732552690890366043312
704 601584543678440275878972
705 627489145500106141664958
706 654490103068322767643970
707 682633104588610309229672
708 711965548791590551224960
709 742536933925035469064346
710 774398612295698182621460
711 807604204347457542505435
712 842209339877930118859174
713 878272098807692758320236
714 915852738409202226857796
715 955014162474306423135526
716 995821633864733444755920
717 1038343273893836117058594
718 1082649759478831352164200
719 1128814854668375720822489
720 1176915091646854339510114
721 1227030336462399496419323
722 1279243453102864868051071
723 1333640905609743318941362
724 1390312404414043452592144
725 1449351547160737133233145
726 1510855446460612439855597
727 1574925411897916840866933
728 1641666558321433740380780
729 1711188531665450195541485
730 1783605096869839801748970
731 1859034910311975281347744
732 1937601086411555535205576
733 2019432019649244886432551
734 2104660928877421668239326
735 2193426732090837899005461
736 2285873567429468462573078
737 2382151724068073929022464
738 2482417138861980730527234
739 2586832386936866461679416
740 2695566152892705114972648
741 2808794284903201062742652
742 2926699239357404229720468
743 3049471202520869038295567
744 3177307507458715140106360
745 3310413827568712418829170
746 3449003564593981321368438
747 3593299118612793364127091
748 3743531245913840160901560
749 3899940410319645749395114
750 4062776109662572313622355
751 4232298313629486123914626
752 4408776757542622955923346
753 4592492472243728399023062
754 4783737043850811442464180
755 4982814241551661220243172
756 5190039241975637051923750
757 5405740361140600774923635
758 5630258242048516211111616
759 5863947697427866573713840
760 6107176859133291131362480
761 6360329138749013852736310
762 6623802337346387155463218
763 6898010731464369557343702
764 7183384141755073820349420
765 7480370152336634621012541
766 7789433136836107287444658
767 8111056619620006573965918
768 8445742257726656540299862
769 8794012353022225901522783
770 9156408788501418841157720
771 9533495700994071800345955
772 9925858370304484604373312
773 10334106062707806999781131
774 10758870871394978759649202
775 11200810741651590733694122
776 11660608261078036458918782
777 12138973878038807458181300
778 12636644640136825957874146
779 13154387618260912023619790
780 13692998591810212451258792
781 14253305691454719583456364
782 14836168029631155697161940
783 15442479575968971884893044
784 16073167731614000009023818
785 16729197452163557235682949
786 17411569764419737103133192
787 18121326152625538292997245
788 18859547016307034867229080
789 19627356336611510722080075
790 20425920073968232869709540
791 21256451132403312225005086
792 22120207695833830365235320
793 23018498509376726231058091
794 23952681153192145385796254
795 24924167661019498033502751
796 25934422730604800581452068
797 26984969700990881093430819
798 28077388698701998676956472
799 29213322996692005465808768
800 30394477095619656396669025
801 31622623488823718701397592
802 32899600678206285915940886
803 34227320371163043026738086
804 35607765430801926901739290
805 37042997532416066873463262
806 38535155048003836210431584
807 40086461191637838706768482
808 41699221838522539548130178
809 43375834190491925247607877
810 45118784530145480632803805
811 46930657439707116420062116
812 48814133491122520488450348
813 50771999053640406753301072
814 52807143921137724751829328
815 54922571746049513694739158
816 57121397605616911276409112
817 59406859102202717609977211
818 61782313870634714056248598
819 64251251387509835835269366
820 66817290422336447951026444
821 69484191601160788295907543
822 72255854804801358055821078
823 75136332535037663251319123
824 78129827263882963503420950
825 81240705653668637587325964
826 84473495862023809720093704
827 87832902670480946421373821
828 91323804750628411686092334
829 94951270759367007051133586
830 98720556572580839350387050
831 102637122408904103468040985
832 106706630038223847626803860
833 110934960999785919362640655
834 115328213793907901603667424
835 119892723264478278759319219
836 124635057783427216288110080
837 129562039872170145691799032
838 134680743389667029553003068
839 139998515472148257924702286
840 145522973736999136777464134
841 151262029625200922078561147
842 157223885634816781540823314
843 163417060156003852195988184
844 169850384749560946392591824
845 176533030570139882860101482
846 183474505707155675873856678
847 190684683297969595001682685
848 198173798950472353907018916
849 205952480654551401223103638
850 214031746307850548583647610
851 222423035540795424080281360
852 231138207369423947264212524
853 240189574056653885866836099
854 249589898918683618811703220
855 259352432353073268767120465
856 269490909828051534910777210
857 280019590216377749309327617
858 290953253999976740845709568
859 302307244057486179824475002
860 314097464119997388337949786
861 326340422169705419412713754
862 339053229186180874666034020
863 352253645323666476216599561
864 365960078991266318503902497
865 380191635987211806145831548
866 394968118960655084986069654
867 410310079692701248321652270
868 426238818992158542763805856
869 442776442325347527198222352
870 459945860203220567336614770
871 477770847374959880643836956
872 496276043769363474369020106
873 515487017481083527485064102
874 535430266335118188924395928
875 556133284909273594384787694
876 577624566797036151676071448
877 599933675925523221947582735
878 623091249598976577471759100
879 647129074388159640041946663
880 672080090044250385133859972
881 697978470253412229093259328
882 724859627519017402965583701
883 752760299094033499198013639
884 781718552938323063914149600
885 811773879161622317780460795
886 842967197172189609914878538
887 875340952984585515394078573
888 908939127686235694448838058
889 943807340987036110984582669
890 979992861141512450804588290
891 1017544715141559633130261623
892 1056513700243882133000695902
893 1096952501233028042461526462
894 1138915703716748710702676286
895 1182459918914005195503475330
896 1227643798894862640764216714
897 1274528169377438380083698196
898 1323176047104022535141801598
899 1373652781162116503303933266
900 1426026072704727946719475658
901 1480366125343837477223015460
902 1536745667440340863021093968
903 1595240112153609760323060548
904 1655927582545440159121534490
905 1718889081906977663832764147
906 1784208521941379106153418696
907 1851972904029400615619777085
908 1922272350777396220280994766
909 1995200298925473653661583443
910 2070853534571054462667178260
911 2149332398468854018948955087
912 2230740825265635080554224484
913 2315186561989541310570949183
914 2402781211659021929525475118
915 2493640465810429969928735234
916 2587884152873520388585245832
917 2685636485640915125797516894
918 2787026114834231425235615466
919 2892186392477228108149281808
920 3001255431110666017933683294
921 3114376384092909975497665282
922 3231697510958231577392271882
923 3353372475734589721581200936
924 3479560418979441807151544232
925 3610426275274618574094978899
926 3746140852516010219657127970
927 3886881169820160980762678605
928 4032830544689652626119394438
929 4184178952645560553096212566
930 4341123122939193922594077440
931 4503866921309186347914752872
932 4672621454962710588944052460
933 4847605479946051190426351490
934 5029045516174749703143429926
935 5217176281002372791119255853
936 5412240815139536711275895050
937 5614490944107613643360894737
938 5824187415951525827961555680
939 6041600392373719999177097740
940 6267009599215326548950552858
941 6500704849181296970476336165
942 6742986206139327569777656498
943 6994164541470044484669815730
944 7254561713313353673298297792
945 7524511158708447560627527322
946 7804358089003346620113865864
947 8094460120088796422868797813
948 8395187485279120557040608028
949 8706923706092314402819715840
950 9030065824009371678278881800
951 9365025114410633366762161914
952 9712227338726947834180533028
953 10072113504310208095089752404
954 10445140138603556829398652126
955 10831780097902689277904895362
956 11232522865294351992103919344
957 11647875411455089885134922194
958 12078362518238079509231068200
959 12524527694858288545751618703
960 12986933529147837535145212234
961 13466162662691796195311471318
962 13962818171922429373130847180
963 14477524605998904129410711601
964 15010928400071637378445737088
965 15563698979942910221186485918
966 16136529210004833803982607032
967 16730136568977198133264842829
968 17345263635207096130897728247
969 17982679338056267587948773939
970 18643179483448008891284582330
971 19327588085769866211640689129
972 20036757936765005781399198920
973 20771572023128488120969924982
974 21532944142066736684986719350
975 22321820410097982183405312976
976 23139179928845865265765059164
977 23986036390908247627491377306
978 24863438799710404370066195998
979 25772473178682607631886394182
980 26714263349275965875779513546
981 27689972750089432601034363886
982 28700805277448369527342845768
983 29748007221547444433236960067
984 30832868174309751511863264018
985 31956723090065061765562880199
986 33120953265747232426664616076
987 34326988534109186068848041382
988 35576308321679880633877800168
989 36870443983030053674369447748
990 38210979942298802822749246320
991 39599556177569488925597053736
992 41037869452191696753748748760
993 42527675958906817505248869454
994 44070792647635636291009052384
995 45669100039610213085798656650
996 47324543658772511567023322934
997 49039137026825609071148280539
998 50814963205896702243010891440
999 52654177986118888863658746973
1000 54559011547754756298339235713