-1 1
0 0
1 3
2 1
3 3
4 6
5 6
6 9
7 15
8 15
9 21
10 30
11 34
12 42
13 60
14 66
15 84
16 108
17 127
18 153
19 201
20 226
21 276
22 342
23 400
24 471
25 585
26 667
27 795
28 954
29 1103
30 1290
31 1551
32 1771
33 2073
34 2442
35 2807
36 3246
37 3816
38 4346
39 5028
40 5838
41 6662
42 7638
43 8856
44 10040
45 11505
46 13212
47 14991
48 17064
49 19560
50 22079
51 25101
52 28578
53 32256
54 36477
55 41448
56 46594
57 52617
58 59490
59 66819
60 75150
61 84792
62 94930
63 106602
64 119802
65 133973
66 149958
67 168201
68 187588
69 209643
70 234396
71 261099
72 290991
73 324771
74 360918
75 401643
76 447066
77 496197
78 550899
79 612210
80 678094
81 751764
82 833538
83 922088
84 1020222
85 1129467
86 1247212
87 1378059
88 1522650
89 1679322
90 1852230
91 2043687
92 2250376
93 2478873
94 2730426
95 3003043
96 3302787
97 3633207
98 3990197
99 4383165
100 4814334
101 5281465
102 5793438
103 6355632
104 6963189
105 7629528
106 8358462
107 9147756
108 10010382
109 10954428
110 11974540
111 13089762
112 14306526
113 15623059
114 17058234
115 18624282
116 20315796
117 22159860
118 24167046
119 26336868
120 28696794
121 31265322
122 34037842
123 37052982
124 40327662
125 43864319
126 47702778
127 51870900
128 56366611
129 61244901
130 66532650
131 72237676
132 78417600
133 85114389
134 92331418
135 100146837
136 108602886
137 117716749
138 127571868
139 138231096
140 149707932
141 162113658
142 175513734
143 189941204
144 205516548
145 222333630
146 240423674
147 259945158
148 280998348
149 303642203
150 328050387
151 354362679
152 382639626
153 413106885
154 445916868
155 481169540
156 519114990
157 559960413
158 603813544
159 650995752
160 701736810
161 756200326
162 814746069
163 877679739
164 945183374
165 1017714333
166 1095616362
167 1179150705
168 1268833782
169 1365115017
170 1468290872
171 1579011753
172 1697788464
173 1825029945
174 1961475858
175 2107784295
176 2264425196
177 2432322972
178 2612231610
179 2804780693
180 3011027706
181 3231932019
182 3468223798
183 3721215144
184 3992012124
185 4281571167
186 4591401018
187 4922893908
188 5277166048
189 5656076970
190 6061240512
191 6494092426
192 6956780142
193 7451316069
194 7979383114
195 8543612787
196 9146346738
197 9789718572
198 10476777798
199 11210421246
200 11993156641
201 12828701682
202 13720436526
203 14671504045
204 15686223600
205 16768748127
206 17922777956
207 19153554459
208 20465933796
209 21864508330
210 23355380448
211 24944480460
212 26637220884
213 28440975336
214 30362688768
215 32409023030
216 34588577379
217 36909786951
218 39380507334
219 42011089107
220 44811420228
221 47791102133
222 50962219890
223 54336725745
224 57925942014
225 61744364523
226 65806011606
227 70124638743
228 74717183466
229 79600519590
230 84790862568
231 90308464485
232 96173119518
233 102404424817
234 109026054819
235 116061744882
236 123534583668
237 131472796188
238 139904223960
239 148856641825
240 158363050986
241 168456720561
242 179170351281
243 190543180620
244 202614222252
245 215422652645
246 229014347898
247 243435781239
248 258733036906
249 274960523319
250 292172713176
251 310424615222
252 329779828674
253 350303055882
254 372058941260
255 395122738413
256 419570239344
257 445478353954
258 472935014016
259 502030007796
260 532853622678
261 565509676992
262 600103271700
263 636741504722
264 675545623338
265 716639833245
266 760149722648
267 806218150722
268 854990388726
269 906615000438
270 961258726470
271 1019092855227
272 1080291401608
273 1145050448799
274 1213570159266
275 1286055866369
276 1362736271928
277 1443846887553
278 1529627942944
279 1620347896281
280 1716281700420
281 1817712166193
282 1924952167230
283 2038324573494
284 2158159868356
285 2284824678918
286 2418695578962
287 2560160793821
288 2709647253291
289 2867596333800
290 3034461165644
291 3210741202911
292 3396950720208
293 3593620948608
294 3801332988153
295 4020688548084
296 4252306938922
297 4496866903974
298 4755068813490
299 5027637355049
300 5315361511878
301 5619059357313
302 5939574738074
303 6277827824217
304 6634769837094
305 7011386456837
306 7408746309090
307 7827958712481
308 8270170074084
309 8736624903657
310 9228611720544
311 9747467377913
312 10294635798285
313 10871617379904
314 11479965161702
315 12121358384010
316 12797537995080
317 13510312154421
318 14261627303766
319 15053507722986
320 15888051570114
321 16767519466431
322 17694257776824
323 18670705635177
324 19699480838490
325 20783307818430
326 21925013706926
327 23127634913334
328 24394326067362
329 25728369005985
330 27133276473300
331 28612706505825
332 30170458752444
333 31810602590739
334 33537369291126
335 35355163541454
336 37268688527730
337 39282844421160
338 41402725302009
339 43633773032475
340 45981649854912
341 48452253197493
342 51051866409642
343 53787038707980
344 56664583203628
345 59691761563515
346 62876133864366
347 66225577627595
348 69748469338332
349 73453542845172
350 77349889172482
351 81447177992406
352 85755481106826
353 90285296953425
354 95047769045910
355 100054519417770
356 105317651164098
357 110850013921263
358 116664996868680
359 122776560313643
360 129199498394982
361 135949243745586
362 143041874053174
363 150494430126714
364 158324673822174
365 166551128758511
366 175193396101194
367 184271926164264
368 193808030722880
369 203824263926781
370 214344140024568
371 225392185845845
372 236994320247510
373 249177587901726
374 261970179687756
375 275401888729941
376 289503782225670
377 304308269111133
378 319849555842330
379 336163337172813
380 353286827712384
381 371259307775442
382 390121743072408
383 409916871949091
384 430689752713323
385 452487405784674
386 475358860475354
387 499355808251175
388 524532163531704
389 550944176108966
390 578651088324750
391 607714722567306
392 638199548628363
393 670173465474246
394 703707295922406
395 738874931428913
396 775754121133896
397 814425998392365
398 854975175715092
399 897490680337209
400 942065375203008
401 988796145329327
402 1037784845187258
403 1089137757856533
404 1142965726639408
405 1199385274827126
406 1258517945233812
407 1320490539883599
408 1385436257625450
409 1453494079615302
410 1524808949384848
411 1599533113360137
412 1677825371239140
413 1759851384018007
414 1845785040304284
415 1935807762241332
416 2030108749306153
417 2128886583531315
418 2232348383499204
419 2340710199827317
420 2454198656595360
421 2573050172745504
422 2697511289298688
423 2827840592212620
424 2964307763760402
425 3107194089781120
426 3256794432316962
427 3413416363086654
428 3577380599386920
429 3749023308468651
430 3928695051722052
431 4116761434621145
432 4313605478403708
433 4519626664630644
434 4735241512169512
435 4960886340217038
436 5197016103373728
437 5444105223560338
438 5702650442820186
439 5973169781589750
440 6256203298214348
441 6552316403784804
442 6862098590210958
443 7186164493838930
444 7525157328886992
445 7879747767182400
446 8250634933069134
447 8638550382794235
448 9044256733407018
449 9468549021027688
450 9912258835638111
451 10376253137150964
452 10861435553049388
453 11368751158886004
454 11899185023747154
455 12453763942831371
456 13033561420107258
457 13639696445415726
458 14273335180393150
459 14935696705626921
460 15628051509354504
461 16351723694956978
462 17108096989518780
463 17898613519878573
464 18724775995295232
465 19588154622220341
466 20490385577632398
467 21433173818269940
468 22418300331724890
469 23447620966872378
470 24523069250653008
471 25646664714574497
472 26820511413685266
473 28046801497340823
474 29327823966562104
475 30665963637443637
476 32063704765706312
477 33523641081707862
478 35048474442003870
479 36641019362720521
480 38304213604432710
481 40041117377597277
482 41854917993901690
483 43748941971038466
484 45726653937704502
485 47791662382259689
486 49947732456840045
487 52198785573361131
488 54548905357592006
489 57002352263736012
490 59563562897754066
491 62237157298540633
492 65027954439245478
493 67940972413360353
494 70981436038725406
495 74154794518186041
496 77466721403192634
497 80923123805242662
498 84530161177926114
499 88294246358256237
500 92222055256779936
501 96320548218408789
502 100596970921552632
503 105058866017910638
504 109714095908119146
505 114570844987548918
506 119637631969552968
507 124923335744913645
508 130437197605443132
509 136188835935354065
510 142188273851771436
511 148445943111301074
512 154972699751755239
513 161779855425282300
514 168879181454841846
515 176282927356030467
516 184003854407715732
517 192055241811855156
518 200450906511174712
519 209205241187172441
520 218333220809777274
521 227850425961796855
522 237773083642819218
523 248118076447076682
524 258902967628498596
525 270146047219622181
526 281866341926869596
527 294083644469878598
528 306818563213262916
529 320092535344804296
530 333927858525133276
531 348347746907899380
532 363376345475425416
533 379038766903196252
534 395361151970954010
535 412370687997553776
536 430095648742210946
537 448565462503397076
538 467810732294754282
539 487863282114153525
540 508756230523004922
541 530524015938229188
542 553202446860497818
543 576828784715750583
544 601441771654303878
545 627081688560720787
546 653790444726245970
547 681611612029270026
548 710590488071988606
549 740774197023932775
550 772211727306829674
551 804954004246696316
552 839053999420731996
553 874566776296605639
554 911549569484648782
555 950061907571734185
556 990165663554026884
557 1031925145731073880
558 1075407231112105362
559 1120681425757196736
560 1167819964124937244
561 1216897958777543262
562 1267993467171280938
563 1321187605254262304
564 1376564710301206380
565 1434212420037211068
566 1494221797014913096
567 1556687511163829040
568 1621707927478881234
569 1689385247846863577
570 1759825709883148536
571 1833139689960000162
572 1909441858724074728
573 1988851403798763480
574 2071492144068061560
575 2157492706566618439
576 2246986769365388514
577 2340113194919034015
578 2437016224284259199
579 2537845748917720629
580 2642757458687555796
581 2751913062274498338
582 2865480583955896650
583 2983634535288568890
584 3106556157372570142
585 3234433752684995955
586 3367462875728680182
587 3505846607375686702
588 3649795917602608914
589 3799529885507149593
590 3955276001156238548
591 4117270570837253346
592 4285758961451700360
593 4460995941670297246
594 4643246125365186366
595 4832784252407633562
596 5029895564335536466
597 5234876299385510343
598 5448034004454755316
599 5669687958929942861
600 5900169716851831173
601 6139823463963336357
602 6389006484741026604
603 6648089767213022766
604 6917458399661151774
605 7197512096658069274
606 7488665862016536102
607 7791350441280909504
608 8106012901726848014
609 8433117371414600841
610 8773145541928360500
611 9126597320657874313
612 9493991641486451388
613 9875867036502757659
614 10272782355547740518
615 10685317669374940167
616 11114074904799046116
617 11559678652771821866
618 12022777159742579604
619 12504043048002037155
620 13004174207446878288
621 13523894899330590240
622 14063956556429557428
623 14625138783210235628
624 15208250568086868408
625 15814131188727943266
626 16443651316161986290
627 17097714363660420918
628 17777257492183864644
629 18483252847188501235
630 19216709040890206404
631 19978672287350782011
632 20770227768159798752
633 21592501280806540032
634 22446660499054177626
635 23333916501014773200
636 24255525581349232884
637 25212790671349440345
638 26207063026559695820
639 27239744240945805786
640 28312287823338893598
641 29426201083716656716
642 30583047348440327280
643 31784447733276634401
644 33032083226905832552
645 34327697151738277329
646 35673097131632315436
647 37070157418335230928
648 38520821598883308867
649 40027104805070286567
650 41591096283355764517
651 43214962400864799003
652 44900949096773668302
653 46651384749168182078
654 48468683483217749058
655 50355347919608675658
656 52313972341555542026
657 54347246366016123204
658 56457957992128421040
659 58648997131040110906
660 60923359647146808972
661 63284150771211075255
662 65734588999763245410
663 68278010577679252359
664 70917873282657904014
665 73657760767714861507
666 76501387496534416926
667 79452602975285707440
668 82515396549614453940
669 85693902876438000270
670 88992406614661377384
671 92415347763038699612
672 95967327685596752514
673 99653114350624805652
674 103477648226832977698
675 107446048960692069045
676 111563621181593467350
677 115835861057900251931
678 120268463650751451990
679 124867329390650573424
680 129638571318562139384
681 134588523231782462955
682 139723746857990453220
683 145051039901037844012
684 150577445012790126618
685 156310257788753624208
686 162257035653543339808
687 168425607794822341800
688 174824084016905151312
689 181460864606976510206
690 188344651276842815544
691 195484457021027407323
692 202889617011150157864
693 210569800705975052817
694 218535022763510971920
695 226795655130074274642
696 235362440379172177806
697 244246503850759409916
698 253459366998008987342
699 263012962144437941919
700 272919645916325119386
701 283192214043962834847
702 293843917616088402351
703 304888478010301287114
704 316340103231349217504
705 328213505886639973716
706 340523919701300376882
707 353287117626248812136
708 366519431636899419468
709 380237771075422851411
710 394459642635476235208
711 409203172248737629620
712 424487125366722424722
713 440330929097740495777
714 456754696311946803204
715 473779248150201438174
716 491426138450289589852
717 509717680383742441800
718 528676971336001861830
719 548327919948457139682
720 568695275453026573830
721 589804655264652431016
722 611682574813481328725
723 634356479948330161797
724 657854777425230947964
725 682206867917044771025
726 707443181695295408889
727 733595212419612432462
728 760695553545068020854
729 788777937722414601687
730 817877274120795835476
731 848029688692474877147
732 879272567554400414076
733 911644598325140693064
734 945185814523790627864
735 979937643454996033641
736 1015942951852297314540
737 1053246094957164342458
738 1091892969235910571330
739 1131931062901182042633
740 1173409510017185523920
741 1216379148668448807669
742 1260892576725003123972
743 1307004211622635910503
744 1354770354392048505474
745 1404249251347777860345
746 1455501159974294969930
747 1508588419552123536339
748 1563575519225816308560
749 1620529170767436899836
750 1679518386305983937748
751 1740614553583715481906
752 1803891516131313339572
753 1869425658976199572368
754 1937295991652137234902
755 2007584236703986990377
756 2080374924000408606450
757 2155755482460280041993
758 2233816337547446473106
759 2314651015229164987146
760 2398356243117862146888
761 2485032058048407088362
762 2574781920452710848828
763 2667712826064462356706
764 2763935424392728112168
765 2863564144751752386510
766 2966717319389720996598
767 3073517314159557442261
768 3184090667150316753084
769 3298568224607351190549
770 3417085284800415243528
771 3539781750731468125104
772 3666802279904697168540
773 3798296442941375913498
774 3934418891523853305588
775 4075329523645076104953
776 4221193658196246413534
777 4372182219903005838450
778 4528471921352315023554
779 4690245455398933195892
780 4857691698511956223290
781 5031005911521710958159
782 5210389951344706879768
783 5396052494831897818824
784 5588209259823371569848
785 5787083238391627519323
786 5992904942922182412024
787 6205912649792267281083
788 6426352655962975914962
789 6654479549783527636704
790 6890556479232387476016
791 7134855434480241037408
792 7387657545525934597338
793 7649253377761980436476
794 7919943242738585760314
795 8200037525599509365253
796 8489857010333894157876
797 8789733221866796932907
798 9100008785858285374272
799 9421037786935384943856
800 9753186144821541353045
801 10096832010035860942272
802 10452366157978075836090
803 10820192402822874589512
804 11200728032231297302806
805 11594404241216920761027
806 12001666587098607685990
807 12422975467438906737426
808 12858806597180124474282
809 13309651509097475084697
810 13776018078737040214170
811 14258431049506568682231
812 14757432582622167311844
813 15273582834068765071458
814 15807460531875579981492
815 16359663580852005452354
816 16930809696137551402500
817 17521537038249033238893
818 18132504877440166961474
819 18764394289826970848493
820 19417908855328075817328
821 20093775387961218193008
822 20792744700065593690602
823 21515592369797887143480
824 22263119543211093539260
825 23036153773707257391459
826 23835549865281664493676
827 24662190753909741229675
828 25516988428897519891176
829 26400884859818430674034
830 27314852964267229201380
831 28259897619608470457445
832 29237056681083963406494
833 30247402044904068345193
834 31292040758435867332884
835 32372116138952997448428
836 33488808940578726147220
837 34643338573041878924127
838 35836964330088944686620
839 37070986670969818394979
840 38346748557450217898520
841 39665636803176951768765
842 41029083479964907013558
843 42438567385132005092493
844 43895615522685066801612
845 45401804647147557524999
846 46958762872878081739602
847 48568171300533935178807
848 50231765710786643403000
849 51951338329996706298948
850 53728739615034332156826
851 55565880112060800142191
852 57464732392580341264872
853 59427333012653744824194
854 61455784551591339702796
855 63552257735499364038666
856 65718993586612364023632
857 67958305659977522598090
858 70272582371337990050082
859 72664289355688255557636
860 75135971919783049717636
861 77690257594739736973674
862 80329858722706279643214
863 83057575146726153678949
864 85876297008273463907343
865 88789007584787880773721
866 91798786238297876247570
867 94908811482152810804598
868 98122364092093783624536
869 101442830339271213539170
870 104873705350412595160452
871 108418596519524303665143
872 112081227050966799089106
873 115865439641937063188889
874 119775200221981835764440
875 123814601836645722584492
876 127987868681309443520088
877 132299360200769419652988
878 136753575344205581435508
879 141355156984738180527450
880 146108896411636120372380
881 151019737992917809677861
882 156092784015393872870373
883 161333299607890600799634
884 166746717848291477224876
885 172338645064942584568398
886 178114866229869514434036
887 184081350553460291279813
888 190244257288824109566390
889 196609941640671330044478
890 203184960891666811073136
891 209976080758353907367502
892 216990281862319589161914
893 224234766439597220910731
894 231716965297871977100466
895 239444544904248835962186
896 247425414730332576033794
897 255667734868508292494586
898 264179923792034944558242
899 272970666396889189412455
900 282048922336507514843022
901 291423934518787939727079
902 301105237907558027052612
903 311102668644467185094979
904 321426373349447829517290
905 332086818754412613005219
906 343094801683185469131030
907 354461459232183916556172
908 366198279311375383106888
909 378317111563858285200258
910 390830178506193773287668
911 403750087062887967371980
912 417089840510184406341606
913 430862850667251534042834
914 445082950513685437533762
915 459764407254447160854885
916 474921935656638089526024
917 490570711852487692432069
918 506726387626240910195778
919 523405105004852558958690
920 540623511353137604996600
921 558398774997702316831794
922 576748601184467532405990
923 595691248587642751806362
924 615245546390793976417212
925 635430911739821246646747
926 656267367792834621358622
927 677775562394967895937133
928 699976787161299299872998
929 722892997212032882252803
930 746546831584040428440432
931 770961634096391482306755
932 796161474922125570718948
933 822171172898612300277255
934 849016318335782369820048
935 876723296595825976611247
936 905319312472502482913493
937 934832415123206015020740
938 965291523836584605287200
939 996726454673054421205602
940 1029167947711152046829976
941 1062647695206290226200688
942 1097198370694792561523094
943 1132853658769361716066332
944 1169648285842996390168936
945 1207618051944497741524344
946 1246799863249488741882840
947 1287231765690431739439740
948 1328952979684056676469688
949 1372003935672628817596839
950 1416426310834407815477398
951 1462263067013174037775701
952 1509558489538804885592088
953 1558358227323734223358331
954 1608709334280187561442910
955 1660660311721916125423554
956 1714261152148736921393132
957 1769563384471581251136288
958 1826620120314913763920722
959 1885486101827667043661347
960 1946217751055169289721550
961 2008873220499841712839599
962 2073512445317108724970898
963 2140197197213322351667839
964 2208991139643987010096272
965 2279959884795308089697582
966 2353171052410420659435624
967 2428694330048610558064053
968 2506601535277919674694143
969 2586966679878519897715278
970 2669866035612818406937860
971 2755378202103440411050885
972 2843584176890839714129230
973 2934567427215574038675933
974 3028413964086109714270914
975 3125212418721854549500164
976 3225054120881001923018808
977 3328033179679461686460742
978 3434246566984796805218598
979 3543794202882807895618176
980 3656779043845428067107174
981 3773307173703961229168469
982 3893487896886486895976916
983 4017433834598701948794963
984 4145261024046364690547082
985 4277089020145146392545752
986 4413041000422577802033172
987 4553243873232815326036083
988 4697828388687571131025854
989 4846929253064304946557368
990 5000685246806522271941820
991 5159239345505369616401688
992 5322738844652483595984102
993 5491335488304261227719476
994 5665185601000347276985800
995 5844450223789186278196550
996 6029295254495011689041580
997 6219891591553724946250017
998 6416415282303281930724162
999 6619047675891407823441015
1000 6827975580077457791030520