-1 1
0 0
1 3
2 3
3 3
4 6
5 7
6 6
7 12
8 16
9 18
10 24
11 33
12 33
13 48
14 57
15 69
16 87
17 106
18 117
19 153
20 181
21 207
22 258
23 307
24 345
25 429
26 496
27 570
28 681
29 805
30 906
31 1083
32 1252
33 1425
34 1671
35 1934
36 2190
37 2562
38 2929
39 3327
40 3840
41 4400
42 4953
43 5727
44 6500
45 7335
46 8388
47 9521
48 10686
49 12198
50 13775
51 15471
52 17529
53 19776
54 22107
55 25017
56 28076
57 31413
58 35343
59 39624
60 44160
61 49608
62 55408
63 61710
64 69063
65 77037
66 85542
67 95565
68 106261
69 117912
70 131265
71 145823
72 161394
73 179391
74 198742
75 219756
76 243597
77 269519
78 297432
79 329202
80 363420
81 400626
82 442383
83 487791
84 536709
85 591906
86 651375
87 715956
88 787980
89 866132
90 950460
91 1044711
92 1146469
93 1256775
94 1378995
95 1511576
96 1654587
97 1813347
98 1984677
99 2170377
100 2374959
101 2596569
102 2835720
103 3099549
104 3384265
105 3692358
106 4030512
107 4396239
108 4790709
109 5223918
110 5691026
111 6195969
112 6747933
113 7344418
114 7987242
115 8690223
116 9447896
117 10265733
118 11156895
119 12118577
120 13154490
121 14283183
122 15498612
123 16809195
124 18232953
125 19767601
126 21419079
127 23213391
128 25143650
129 27222414
130 29475222
131 31900304
132 34507764
133 37332936
134 40369759
135 43636119
136 47167812
137 50965440
138 55044450
139 59453838
140 64188686
141 69276099
142 74765265
143 80660871
144 86987598
145 93812016
146 101133233
147 108990447
148 117453192
149 126532082
150 136265271
151 146744814
152 157975853
153 170016339
154 182962545
155 196837181
156 211696986
157 227668746
158 244769983
159 263083998
160 282745620
161 303794871
162 326318262
163 350488893
164 376344119
165 404005527
166 433659585
167 465375016
168 499279407
169 535612503
170 574441282
171 615941682
172 660373917
173 707848040
174 758553078
175 812817990
176 870759239
177 932627955
178 998786037
179 1069408319
180 1144769211
181 1225322808
182 1311257380
183 1402934841
184 1500855282
185 1605288598
186 1716634335
187 1835515512
188 1962230278
189 2097293457
190 2241400896
191 2394958654
192 2558543100
193 2733012975
194 2918824176
195 3116710086
196 3327632418
197 3552200252
198 3791236344
199 4045922211
200 4316947504
201 4605347442
202 4912453833
203 5239162502
204 5586649200
205 5956533966
206 6349841937
207 6768034995
208 7212948537
209 7685891745
210 8188528731
211 8723087757
212 9291068123
213 9894524166
214 10535988087
215 11217348301
216 11940954948
217 12709861059
218 13526247130
219 14392983507
220 15313555104
221 16290672337
222 17327630556
223 18428614650
224 19596756238
225 20836063548
226 22151317098
227 23546375764
228 25025849823
229 26595457998
230 28259670007
231 30024052239
232 31895163801
233 33878454664
234 35980344813
235 38208647643
236 40569685566
237 43071171906
238 45722075409
239 48530064171
240 51504033864
241 54654638340
242 57990775961
243 61523086752
244 65263820064
245 69223690642
246 73414997382
247 77852231283
248 82547838009
249 87516461820
250 92774783208
251 98337711471
252 104222172435
253 110447861487
254 117032080399
255 123994916004
256 131359051149
257 139145117331
258 147376342800
259 156079426134
260 165278326728
261 175000498110
262 185276713359
263 196135417152
264 207608362008
265 219731685756
266 232538393129
267 246065922522
268 260355916224
269 275447422896
270 291383732004
271 308213638515
272 325982433285
273 344740996671
274 364545589329
275 385449591271
276 407511832257
277 430798089093
278 455370239586
279 481297258830
280 508654962255
281 537516092005
282 567960339228
283 600076183413
284 633947876551
285 669668636553
286 707340433392
287 747062016853
288 788941071012
289 833096345118
290 879642140070
291 928704132468
292 980419139271
293 1034920802832
294 1092354192075
295 1152878402103
296 1216647952665
297 1283831827116
298 1354613239914
299 1429172448312
300 1507704393366
301 1590421741548
302 1677532773813
303 1769264093445
304 1865860509831
305 1967564465610
306 2074637194980
307 2187362428434
308 2306020010550
309 2430913120185
310 2562368141301
311 2700710200032
312 2846288532183
313 2999480857671
314 3160662124192
315 3330236925477
316 3508639561734
317 3696304792792
318 3893698339563
319 4101322082700
320 4319676940075
321 4549301617491
322 4790772752856
323 5044670241100
324 5311613613054
325 5592268365579
326 5887301983844
327 6197430025923
328 6523416606156
329 6866033145641
330 7226101961490
331 7604503700778
332 8002125496172
333 8419915751826
334 8858884898355
335 9320056657335
336 9804519959436
337 10313437971660
338 10847986772817
339 11409420602046
340 11999073030579
341 12618299261784
342 13268538175830
343 13951323020307
344 14668209320563
345 15420852153666
346 16211008101174
347 17040467111635
348 17911126304568
349 18825002961675
350 19784149615809
351 20790745847190
352 21847100889483
353 22955573557650
354 24118660009206
355 25339009250169
356 26619323643843
357 27962467504173
358 29371470979923
359 30849435681218
360 32399639210679
361 34025553764970
362 35730729435424
363 37518922960779
364 39394102908966
365 41360339124913
366 43421926609932
367 45583408179543
368 47849437888147
369 50224933188555
370 52715082257631
371 55325214288735
372 58060946708622
373 60928212227961
374 63933099631588
375 67082033551074
376 70381784184354
377 73839315907701
378 77461961581167
379 81257455502085
380 85233747500417
381 89399215584309
382 93762678853362
383 98333220684771
384 103120395536100
385 108134268562521
386 113385199602543
387 118884093819189
388 124642419182724
389 130672000472742
390 136985263942605
391 143595285681054
392 150515540445124
393 157760197678896
394 165344144095080
395 173282744656438
396 181592131984851
397 190289264865246
398 199391637478133
399 208917628112448
400 218886529116726
401 229318269242735
402 240233756362521
403 251654948497578
404 263604517218845
405 276106259065629
406 289185134159115
407 302866945300675
408 317178742590702
409 332148910429584
410 347806778800715
411 364183107735675
412 381310137873498
413 399221219526081
414 417951291268200
415 437536985451000
416 458016180952783
417 479428573651242
418 501815741407668
419 525220717308563
420 549688554542040
421 575266455789531
422 602003258514781
423 629950107332445
424 659160537492936
425 689689984205216
426 721596450329892
427 754940664067197
428 789785489313683
429 826196716526445
430 864243170552430
431 903996148129820
432 945530205895671
433 988923354124299
434 1034256381690739
435 1081613787705462
436 1131083918610270
437 1182758326115406
438 1236732697326081
439 1293107091793614
440 1351985172160811
441 1413475300137141
442 1477690712191119
443 1544748787094886
444 1614772144833228
445 1687888937261811
446 1764231972491971
447 1843940005803378
448 1927157962510926
449 2014036106890853
450 2104731338464998
451 2199407549978865
452 2298234634167640
453 2401390002915114
454 2509058871257946
455 2621433315995127
456 2738713807004838
457 2861109646138656
458 2988837845676341
459 3122124916662651
460 3261207228245418
461 3406329947313670
462 3557748845700804
463 3715730841149319
464 3880552733075734
465 4052503309730910
466 4231883802447894
467 4419006694577358
468 4614197856913980
469 4817797212573723
470 5030157320135455
471 5251645854282672
472 5482646180735685
473 5723556024995201
474 5974789994177835
475 6236780397224949
476 6509975661772770
477 6794843258314287
478 7091870423258130
479 7401562680681967
480 7724446821877620
481 8061071915220615
482 8412007548773432
483 8777847275807292
484 9159209526161199
485 9556735971349332
486 9971095048279572
487 10402983203684247
488 10853122952097815
489 11322266940507231
490 11811199091982216
491 12320732813387356
492 12851715160468830
493 13405028374140750
494 13981587748996877
495 14582346427820457
496 15208296838188063
497 15860468740393031
498 16539934156934994
499 17247809264927865
500 17985252077116386
501 18753468100944483
502 19553712137225877
503 20387286177962784
504 21255545239676037
505 22159899699417531
506 23101812790306383
507 24082807287791568
508 25104467759448111
509 26168438324481775
510 27276429564619626
511 28430221403376216
512 29631660435360265
513 30882667825700310
514 32185242123726894
515 33541456910145248
516 34953468985410450
517 36423521923310238
518 37953943257383601
519 39547153825214163
520 41205671276610474
521 42932107651948082
522 44729179091030742
523 46599710213868033
524 48546631212017699
525 50572988904407919
526 52681951112582430
527 54876804223888249
528 57160964714506482
529 59537984550177024
530 62011548243124797
531 64585485947962917
532 67263778905755595
533 70050557081733660
534 72950112843246198
535 75966907620828345
536 79105569023153879
537 82370906355547074
538 85767917392876773
539 89301786202409075
540 92977899398249994
541 96801854346150948
542 100779456468236273
543 104916737647301622
544 109219964637210915
545 113695637233670503
546 118350507596815101
547 123191590362869280
548 128226160303447093
549 133461774174288678
550 138906281149253826
551 144567821542444051
552 150454849801986216
553 156576146958944307
554 162940818878589647
555 169558322208240198
556 176438477314018476
557 183591467829299846
558 191027868029207907
559 198758658159671871
560 206795223575797068
561 215149385591770635
562 223833417492614958
563 232860045271968544
564 242242480246361262
565 251994437913987279
566 262130138382056612
567 272664343063411659
568 283612374485818185
569 294990118669417177
570 306814064017876890
571 319101324510594708
572 331869641920329467
573 345137429508257928
574 358923796496072970
575 373248552683493408
576 388132254842423772
577 403596235231982976
578 419662606258906319
579 436354312534690575
580 453695161090669503
581 471709828977382479
582 490423918659722472
583 509863993042504242
584 530057583411677446
585 551033251501143936
586 572820626751600558
587 595450417854714008
588 618954478925159430
589 643365852515037798
590 668718781873458335
591 695048785009543770
592 722392700596707546
593 750788704652646371
594 780276389648026032
595 810896817286882377
596 842692536423893272
597 875707671484092177
598 909987978977323800
599 945580870822815824
600 982535508966437019
601 1020902870122148997
602 1060735770998331687
603 1102088973944094180
604 1145019256442720478
605 1189585442977897074
606 1235848518266434851
607 1283871706608265680
608 1333720506518500689
609 1385462817017087220
610 1439169023026694136
611 1494912038114276640
612 1552767440086367892
613 1612813568187364296
614 1675131569720608714
615 1739805551121898923
616 1806922682789960886
617 1876573255646060505
618 1948850843564301660
619 2023852422372209826
620 2101678431689313139
621 2182432955729074725
622 2266223851894069581
623 2353162824762242848
624 2443365620776536162
625 2536952173817859861
626 2634046686275682048
627 2734777845541776303
628 2839278981603162654
629 2947688162959198128
630 3060148430052030936
631 3176807973257891421
632 3297820238111101740
633 3423344184673320591
634 3553544480505812766
635 3688591624034781800
636 3828662224563246360
637 3973939219731800001
638 4124612011021811805
639 4280876774590960611
640 4442936697390955563
641 4611002134798140546
642 4785290946593108541
643 4966028762496502779
644 5153449155439091477
645 5347794014250832611
646 5549313832298831061
647 5758267907777565393
648 5974924746969362493
649 6199562388242198067
650 6432468622339788557
651 6673941439353462894
652 6924289381315066077
653 7183831795388083944
654 7452899318031055347
655 7731834270071781108
656 8020990935310662791
657 8320736096773848468
658 8631449467055298459
659 8953524007022038328
660 9287366507197095618
661 9633398069205920316
662 9992054456548096609
663 10363786738098577419
664 10749061812968479959
665 11148362810075594698
666 11562189786438354516
667 11991060313437567384
668 12435509916711942526
669 12896092848528666579
670 13373382727392279471
671 13867973037291446733
672 14380477966493042847
673 14911533121008846234
674 15461796074232262608
675 16031947294176496917
676 16622690922330534684
677 17234755395441972017
678 17868894453230767374
679 18525888006035474130
680 19206542819409433132
681 19911693627371353653
682 20642204080140236379
683 21398967516321892256
684 22182908173602363702
685 22994982243235877601
686 23836178720197055618
687 24707520739943370990
688 25610066730724202454
689 26544911370080036589
690 27513187039458773832
691 28516065104880843600
692 29554756969925846130
693 30630515680921550253
694 31744637327015878107
695 32898462222066254657
696 34093376652360923331
697 35330814430950934449
698 36612258198628546961
699 37939241351543731959
700 39313349741013299913
701 40736223130744235875
702 42209557296576499398
703 43735105911756173649
704 45314682150706833387
705 46950161003755571202
706 48643481339427272727
707 50396647697386966827
708 52211732811018329478
709 54090879892511063610
710 56036304605829882455
711 58050297846176636028
712 60135228240229732125
713 62293544348003100543
714 64527777693052181514
715 66840545530429357761
716 69234553269056792404
717 71712597809027279565
718 74277570570671236506
719 76932460193700203323
720 79680356176820080908
721 82524452228324267805
722 85468049234961006413
723 88514559268508994963
724 91667509253028432924
725 94930544268078820954
726 98307431919572956152
727 101802066393099037503
728 105418472086342853797
729 109160808418607975634
730 113033374267547581116
731 117040612005351834347
732 121187112746854386879
733 125477621249726259129
734 129917040351803030424
735 134510436743445474033
736 139263046331664098718
737 144180279164484563762
738 149267725731189712698
739 154531162882542404634
740 159976559243190564892
741 165610082138435923329
742 171438104075136913068
743 177467208741386442205
744 183704198568021999084
745 190156101876723513090
746 196830179472463642869
747 203733932953724845632
748 210875112537584430864
749 218261724359679067058
750 225902039547410049198
751 233804602844982368088
752 241978240632520700353
753 250432070893763342997
754 259175512657801462536
755 268218294870019934776
756 277570467276249021660
757 287242410823510185858
758 297244847401996720202
759 307588851797913538923
760 318285863078472758208
761 329347695358786408700
762 340786550854891980798
763 352615032417831583158
764 364846155354481378470
765 377493361756861138101
766 390570534221587283544
767 404092008902915181239
768 418072591162067150628
769 432527570663010191400
770 447472735699041066996
771 462924390366279592389
772 478899371085532363977
773 495415062409578397437
774 512489415779385691065
775 530140967693846639622
776 548388857054267916034
777 567252845740174438356
778 586753338493644497592
779 606911402041580352595
780 627748787568402231693
781 649287952572393830565
782 671552081841463883183
783 694565112097612367907
784 718351755912943866555
785 742937524818840941603
786 768348756222184148082
787 794612639680543301406
788 821757242243726196057
789 849811537961475027597
790 878805436631010023808
791 908769811696902032440
792 939736532478304135872
793 971738495737205041248
794 1004809656264660640964
795 1038985062199246592550
796 1074300889560896250309
797 1110794475903111006411
798 1148504358884948989401
799 1187470314176286450465
800 1227733392339170551804
801 1269335961086365255530
802 1312321746741064529175
803 1356735874790375687404
804 1402624916034180915324
805 1450036932072436425645
806 1499021519737134759229
807 1549629861635832148392
808 1601914775896566344292
809 1655930764995001336196
810 1711734070947215310468
811 1769382729863949102012
812 1828936625431760462312
813 1890457549343328820047
814 1954009260947556942183
815 2019657545988512304504
816 2087470282588763316792
817 2157517506639727005987
818 2229871476120560496553
819 2304606743321075204454
820 2381800226327608628151
821 2461531279627222557485
822 2543881772959987837761
823 2628936169652784379428
824 2716781603908209251888
825 2807507967087673863048
826 2901207993331383413529
827 2997977344356935147269
828 3097914703651921793130
829 3201121870259935797495
830 3307703851580738532072
831 3417768966409215004740
832 3531428947425266396751
833 3648799042960906292774
834 3769998129471676562292
835 3895148823759132301956
836 4024377594308939998367
837 4157814884289627732426
838 4295595234166052942853
839 4437857403738283290715
840 4584744506382739824942
841 4736404143260551389372
842 4892988536795417628906
843 5054654677438296439944
844 5221564470272844347676
845 5393884881255916640391
846 5571788097375035372946
847 5755451687060429127936
848 5945058760087865448345
849 6140798142627844662816
850 6342864552439748130858
851 6551458773987412967223
852 6766787849434722896130
853 6989065270272310923360
854 7218511168738997932698
855 7455352526518922894958
856 7699823383982826320937
857 7952165049733130026894
858 8212626328277917567497
859 8481463748821069782966
860 8758941794254997942697
861 9045333149867280337350
862 9340918953109101254307
863 9645989044166534893978
864 9960842237239679132421
865 10285786593555839895990
866 10621139695120220745499
867 10967228940975764740578
868 11324391845185749546678
869 11692976336263282977256
870 12073341080266073401614
871 12465855806406152583441
872 12870901634088102177045
873 13288871425661766109062
874 13720170141735056748774
875 14165215198753119900754
876 14624436853638370687614
877 15098278591922467089024
878 15587197518189772588995
879 16091664775913387608236
880 16612165970901678673221
881 17149201598046010142095
882 17703287499028382561511
883 18274955324737660059303
884 18864753001111984435925
885 19473245228598254745870
886 20101013986530832345281
887 20748659042106317831960
888 21416798494800094000800
889 22106069326995549159753
890 22817127959437796053926
891 23550650845157170245723
892 24307335069934221736752
893 25087898958970532016555
894 25893082724154571944852
895 26723649119392870855986
896 27580384102504971403181
897 28464097541168550679782
898 29375623927403784163944
899 30315823100254892243408
900 31285581014995733890515
901 32285810522670861591861
902 33317452158353544646159
903 34381474979872383366267
904 35478877417529241140544
905 36610688134462589580611
906 37777966940362006843134
907 38981805718289601204744
908 40223329362868227210638
909 41503696776327528573309
910 42824101878536009444370
911 44185774630678687308952
912 45589982120148554999640
913 47038029661918753429053
914 48531261914528336425984
915 50071064062435571238441
916 51658863016004717462658
917 53296128628797558059169
918 54984374985142350448914
919 56725161708274479893358
920 58520095287055265448994
921 60370830478864166417241
922 62279071734550455563139
923 64246574645140531262216
924 66275147469272911873434
925 68366652686155720463829
926 70523008571922591851460
927 72746190863469638886258
928 75038234449707682444200
929 77401235089964838647228
930 79837351225175344827384
931 82348805820563361906249
932 84937888237571631205577
933 87606956206313615999634
934 90358437831907414641876
935 93194833634481091013027
936 96118718695882906256736
937 99132744845078788606062
938 102239642879861563961502
939 105442224904138827939687
940 108743386706887430471361
941 112146110182644668388101
942 115653465874778139116694
943 119268615566082812779956
944 122994814914214175374585
945 126835416220082693106306
946 130793871247271457881937
947 134873734092450742226418
948 139078664197144884041787
949 143412429417185949612096
950 147878909147258502692095
951 152482097598489147072126
952 157226107138277865500250
953 162115171692486115951246
954 167153650310444086290156
955 172346030800046838702720
956 177696933430252927982724
957 183211114809838504500093
958 188893471841824540123068
959 194749045753870293097197
960 200783026316312197265172
961 207000756145108962688497
962 213407735086943338491630
963 220009624807415948058942
964 226812253470961732220760
965 233821620513013200644587
966 241043901628526401559382
967 248485453863094684381314
968 256152820803862914017087
969 264052738004578184096385
970 272192138521511591515401
971 280578158561066421242302
972 289218143376984644338542
973 298119653291204363314446
974 307290469835588143595391
975 316738602163706962202595
976 326472293596311165682827
977 336500028301664361951293
978 346830538263949405459215
979 357472810400388749652870
980 368436093824352580995393
981 379729907420102969984787
982 391364047578366735184353
983 403348596094367270591614
984 415693928398480870978422
985 428410721965388285428446
986 441509964899117278575287
987 455002964877863911662717
988 468901358291896103072805
989 483217119576722790638093
990 497962570930498498239939
991 513150392245267834940631
992 528793631249649103588786
993 544905714067060509431745
994 561500456005302931570131
995 578592072580368224774758
996 596195190984279122957928
997 614324861808674375077680
998 632996571022038426965678
999 652226252427077574515367
1000 672030300394826977910766