-1 1
0 0
1 3
2 2
3 5
4 6
5 12
6 12
7 22
8 22
9 39
10 40
11 63
12 68
13 106
14 112
15 164
16 182
17 257
18 282
19 390
20 432
21 584
22 652
23 859
24 964
25 1253
26 1404
27 1794
28 2024
29 2556
30 2880
31 3594
32 4054
33 5016
34 5662
35 6930
36 7830
37 9516
38 10744
39 12959
40 14640
41 17546
42 19800
43 23590
44 26612
45 31536
46 35560
47 41919
48 47236
49 55443
50 62422
51 72941
52 82076
53 95538
54 107400
55 124558
56 139912
57 161716
58 181496
59 209094
60 234464
61 269336
62 301728
63 345621
64 386870
65 441984
66 494256
67 563282
68 629338
69 715556
70 798752
71 906146
72 1010598
73 1144122
74 1274832
75 1440373
76 1603544
77 1808364
78 2011416
79 2264264
80 2516336
81 2827827
82 3139932
83 3522814
84 3908336
85 4378124
86 4853136
87 5428338
88 6012404
89 6715406
90 7431864
91 8289442
92 9166528
93 10210820
94 11282320
95 12551679
96 13858116
97 15398582
98 16988330
99 18854529
100 20785586
101 23042874
102 25384116
103 28110078
104 30943804
105 34230728
106 37654660
107 41611935
108 45742200
109 50499760
110 55473952
111 61185218
112 67166664
113 74013374
114 81194880
115 89391480
116 98001200
117 107800758
118 118107840
119 129808345
120 142130080
121 156082711
122 170792560
123 187409634
124 204947304
125 224713552
126 245595024
127 269078943
128 293910294
129 321778364
130 351269920
131 384302265
132 419286072
133 458395820
134 499845104
135 546098721
136 595151690
137 649794910
138 707779896
139 772265575
140 840732928
141 916754508
142 997510904
143 1087039819
144 1182189318
145 1287519924
146 1399510148
147 1523308371
148 1654985432
149 1800348418
150 1955016708
151 2125538044
152 2307033304
153 2506880109
154 2719649272
155 2953648974
156 3202844456
157 3476586702
158 3768172600
159 4088121945
160 4428998256
161 4802628264
162 5200768722
163 5636710925
164 6101326244
165 6609543396
166 7151262912
167 7743244637
168 8374327024
169 9063316941
170 9797888600
171 10599137370
172 11453467904
173 12384529408
174 13377339648
175 14458402101
176 15611222836
177 16865490132
178 18203064092
179 19657186954
180 21207930672
181 22892501908
182 24689028096
183 26639138275
184 28718854368
185 30974732628
186 33380513496
187 35988247567
188 38769208832
189 41781567948
190 44993935904
191 48471300306
192 52179404164
193 56190825846
194 60468218908
195 65092613990
196 70023350742
197 75350862836
198 81030935340
199 87164468737
200 93703445858
201 100760408084
202 108283279388
203 116397547700
204 125046816764
205 134370969208
206 144309014752
207 155016839805
208 166428592188
209 178717939404
210 191813890320
211 205909875345
212 220929492876
213 237088124776
214 254303692276
215 272815958359
216 292536914616
217 313733397664
218 336311222760
219 360567288174
220 386401021536
221 414142682862
222 443685120048
223 475395626192
224 509160320072
225 545387582937
226 583956703172
227 625321646161
228 669354834832
229 716560796974
230 766805117440
231 820648403988
232 877949539248
233 939331306178
234 1004646117852
235 1074585698212
236 1148996361872
237 1228646247948
238 1313376097936
239 1404038743867
240 1500470072992
241 1603616768286
242 1713310783082
243 1830602791131
244 1955322009560
245 2088634302944
246 2230367631144
247 2381815462092
248 2542806332040
249 2714775021412
250 2897552875920
251 3092731156990
252 3300146726376
253 3521564097216
254 3756828868912
255 4007897355503
256 4274627759606
257 4559188680862
258 4861455474672
259 5183831698118
260 5526215229664
261 5891269615968
262 6278921550548
263 6692122242499
264 7130834559864
265 7598327948064
266 8094609985456
267 8623302142742
268 9184466648544
269 9782114295868
270 10416373430112
271 11091685401455
272 11808257914026
273 12571008383384
274 13380239108868
275 14241393837665
276 15154886975360
277 16126744098688
278 17157511750852
279 18253858622130
280 19416486355008
281 20652774366662
282 21963605577792
283 23357144808421
284 24834486119104
285 26404662105496
286 28069011948984
287 29837526935202
288 31711830007590
289 33702971443447
290 35812901760528
291 38053840901254
292 40428116681292
293 42949240740866
294 45619974440556
295 48455255773075
296 51458343275416
297 54645749739024
298 58021302747164
299 61603253597742
300 65396080046860
301 69419952381336
302 73680089929072
303 78198780949102
304 82982089357528
305 88054640655484
306 93423459200646
307 99115749470466
308 105139626546608
309 111525140199592
310 118281642569856
311 125442322184063
312 133017932522344
313 141045124157690
314 149536236089308
315 158531737081314
316 168045758162928
317 178122978470896
318 188779552262520
319 200064801032747
320 211997161050992
321 224631071752504
322 237987540829160
323 252126649286012
324 267072299747358
325 282890791194838
326 299609282451284
327 317300924942346
328 335996537097348
329 355776820937448
330 376676704466544
331 398785208648552
332 422141872836592
333 446844882191448
334 472938946577216
335 500532345239347
336 529675581405616
337 560488051194134
338 593026744465486
339 627423299095988
340 663741963102544
341 702127852956784
342 742653332738904
343 785478357533986
344 830684361177408
345 878447632344152
346 928859734204680
347 982114932314301
348 1038316095959904
349 1097677273557010
350 1160313946660144
351 1226461931132406
352 1296250770243316
353 1369940227649598
354 1447675515757488
355 1529742741440022
356 1616304568355516
357 1707676077575096
358 1804039358873944
359 1905741357070240
360 2012985775761456
361 2126154596472559
362 2245475558904016
363 2371369165075439
364 2504089872183504
365 2644100527008544
366 2791685270912976
367 2947353493283750
368 3111422301039136
369 3284452232991666
370 3466796989651568
371 3659073314471986
372 3861675511588208
373 4075282075417130
374 4300332344097332
375 4537572647418321
376 4787492251160960
377 5050911993906664
378 5328376472055168
379 5620788351906105
380 5928753524215360
381 6253264508168680
382 6594995069257088
383 6955036378216365
384 7334137333928132
385 7733497403825208
386 8153948624117276
387 8596809330654036
388 9063003520625428
389 9553979983538582
390 10070764401272544
391 10614948711719953
392 11187670994283366
393 11790680243044328
394 12425238733800272
395 13093267751863258
396 13796166760916244
397 14536046023813548
398 15314456492205880
399 16133715679901005
400 16995541763354562
401 17902479515413350
402 18856431649680192
403 19860192103088176
404 20915867167334620
405 22026523921014552
406 23194493170146144
407 24423141377956522
408 25715046879114364
409 27073904239451246
410 28502564613779664
411 30005082092670150
412 31584608438802624
413 33245591642865624
414 34991514596968104
415 36827256793635706
416 38756665771030908
417 40785093647463800
418 42916789403236288
419 45157622752771011
420 47512284505394048
421 49987211140695978
422 52587579613647052
423 55320446921437320
424 58191524782931244
425 61208549466796791
426 64377820779398904
427 67707818473560454
428 71205488914685676
429 74880125507122164
430 78739385276538240
431 82793451942963901
432 87050763449681976
433 91522477582513646
434 96217890188780568
435 101149224598489218
436 106326718905582800
437 111763761888967172
438 117471626268998424
439 123464975366612246
440 129756217690431008
441 136361410211674359
442 143294207981545028
443 150572191646966050
444 158210384032777424
445 166228031384252708
446 174641656969562320
447 183472327519493239
448 192738211904520392
449 202462366352027358
450 212664764124147966
451 223370635343630548
452 234601931329581340
453 246386257257554296
454 258747732399356708
455 271716556393106058
456 285319224065330576
457 299588768800908030
458 314554287893941108
459 330251909399262426
460 346713581051749440
461 363978810054425282
462 382082665516190208
463 401068343907069882
464 420974331673566064
465 441847852574237312
466 463731133636865524
467 486675794294046816
468 510728155127079996
469 535944632663620012
470 562376026399416992
471 590083987317023933
472 619124214472475088
473 649564069752632052
474 681464610848107704
475 714899429514434550
476 749935443000495768
477 786653038123984890
478 825125538180162848
479 865440740507875843
480 907678970539799712
481 951936106239139216
482 998300125254543708
483 1046875715675145536
484 1097759216199124358
485 1151064919097756568
486 1206898296879269028
487 1265384110207545981
488 1326637807709665304
489 1390795558875912528
490 1457983706409357464
491 1528350851872436182
492 1602035232274177560
493 1679198994449788476
494 1759993359403879888
495 1844595230148643710
496 1933169998638904136
497 2025910641070410832
498 2122998013030447824
499 2224642596119117255
500 2331042117153555232
501 2442426120444014320
502 2559010736512612144
503 2681046265475985487
504 2808768909722765640
505 2942451565661279696
506 3082352323112141592
507 3228768675221562873
508 3381982574924121568
509 3542318286128753554
510 3710083774456670400
511 3885632436943401117
512 4069300590299089110
513 4261473331369556424
514 4462517871372854836
515 4672853795285328514
516 4892881974814470656
517 5123059511773057044
518 5363823945909279296
519 5615673185270127179
520 5879084707366696800
521 6154600798550973050
522 6442742428296945384
523 6744100139810562868
524 7059242257376645100
525 7388811791840457880
526 7733428619963898784
527 8093792791141278539
528 8470580295438935736
529 8864553182009451947
530 9276448508892858896
531 9707095709164738842
532 10157298290573890080
533 10627958912565436916
534 11119953377348058552
535 11634263909691785860
536 12171844952951237472
537 12733765174023427092
538 13321064548138853176
539 13934905643690882589
540 14576421448127008704
541 15246876521629727180
542 15947504983106223520
543 16679682158037803471
544 17444752108266485642
545 18244210437831173604
546 19079520712884394848
547 19952309130157935829
548 20864169133769278020
549 21816868694215795788
550 22812142386956096836
551 23851912075676143724
552 24938065673198621824
553 26072692071339146400
554 27257845757781610664
555 28495796886322263464
556 29788780873698446940
557 31139264558540409442
558 32549679849615528288
559 34022706979588188757
560 35560991220549447488
561 37167444299879970600
562 38844943140143808668
563 40596650569173184042
564 42425694979203050112
565 44335511531949337976
566 46329501566074441532
567 48411395570751659586
568 50584891100972560736
569 52854038870077458462
570 55222857858850202784
571 57695745959039931359
572 60277070884379518472
573 62971606883450448988
574 65784099978519679040
575 68719732357502542622
576 71783660379555527046
577 74981508352650864054
578 78318877652948843970
579 81801871696941196180
580 85436574424473156736
581 89229608382821735832
582 93187580720577567432
583 97317676415795597870
584 101627069819434023788
585 106123555181165173584
586 110814921666438934524
587 115709623462076096468
588 120816116069896314084
589 126143568410223978620
590 131701158067064820352
591 137498827951586955453
592 143546538038661687768
593 149855069304637610302
594 156435229352313019056
595 163298706498436843670
596 170457226533389890004
597 177923460004270076084
598 185710127196357625104
599 193830961837930102724
600 202299761222464401932
601 211131409752019566426
602 220340870941632639312
603 229944274419823863120
604 239957846369254907648
605 250399063816211667248
606 261285519863810674776
607 272636149327930218782
608 284470024910455742296
609 296807658477688343616
610 309669724100801480688
611 323078439525020346336
612 337056211771940590794
613 351627103614491812770
614 366815397190427651592
615 382647150580110268425
616 399148674621620348976
617 416348184986512208626
618 434274187113929936928
619 452957229494677600697
620 472428191353640067328
621 492720143185668059724
622 513866531511786905280
623 535903153062558084695
624 558866230613110647784
625 582794507581845509175
626 607727208611406866252
627 633706261744005837558
628 660774137059123631140
629 688976204002442210668
630 718358441015415010752
631 748969936034154792660
632 780860459649924457232
633 814083117258570345112
634 848691777873518157808
635 884743886896885903910
636 922297742266514045064
637 961415477338176937190
638 1002160175584405293344
639 1044599033624830243089
640 1088800305205814023792
641 1134836654994429931950
642 1182781922052962008608
643 1232714675623183788825
644 1284714787767165306432
645 1338867203014064495744
646 1395258309267092086152
647 1453979933866932572808
648 1515125501262569506158
649 1578794268765678912892
650 1645087258848797429108
651 1714111748625758765426
652 1785976963972721429020
653 1860798837573060486324
654 1938695451353397192672
655 2019792078779812239583
656 2104216361360313186756
657 2192103651775158149322
658 2283591909417410635584
659 2378827361886235727152
660 2477959103716218482112
661 2581145094761430883894
662 2688546445400011439360
663 2800333771391578382153
664 2916681147933965236656
665 3037772841690096766048
666 3163796915116530058080
667 3294952357531613745506
668 3431442320128063494152
669 3573481669195348489332
670 3721289831168594322720
671 3875098792428349657745
672 4035145532622884741808
673 4201680496851513302558
674 4374959594324161569076
675 4555253170194325488144
676 4742837545385692307514
677 4938004516881635151436
678 5141052413250737038680
679 5352296153826089499208
680 5572057793096471095760
681 5800677170925116485296
682 6038501917537927040056
683 6285898728742818728585
684 6543242801737055400600
685 6810929771199886206204
686 7089364544554352126624
687 7378973936823244875744
688 7680194872312693269952
689 7993487758250073404108
690 8319324018103456744944
691 8658200246266271733243
692 9010625036383943135040
693 9377133961720033095912
694 9758275659925009090260
695 10154627686219117308637
696 10566781814003439776160
697 10995360810632891155102
698 11441002911131915357316
699 11904379569114339427446
700 12386179058620179716792
701 12887125255675278614194
702 13407960320906659546416
703 13949464570332482986810
704 14512438188935553931828
705 15097722252541666972440
706 15706179419928830160316
707 16338716171098862223300
708 16996262422767492376416
709 17679795051969739179452
710 18390316376907207570336
711 19128879038662679943264
712 19896563286369113547612
713 20694503293853512802496
714 21523863184930711777320
715 22385864866062639783996
716 23281762724261641860344
717 24212873061350372464540
718 25180547393477122022896
719 26186203577306522542718
720 27231297636495155192304
721 28317356675147187742040
722 29445949152764566903114
723 30618719685578771626992
724 31837357687467688224216
725 33103634165339268611468
726 34419368639288180381868
727 35786468044075191449456
728 37206891837371477983696
729 38682693125565033737583
730 40215981864299996462800
731 41808968333365694434832
732 43463924328872311944400
733 45183229118857347897974
734 46969328521337248901864
735 48824783479519362322050
736 50752226914620976138016
737 52754415067222061497004
738 54834182008137471826188
739 56994493900508525862782
740 59238401046138928012480
741 61569095231423496045712
742 63989859180401979292160
743 66504127156584721059857
744 69115431687527973298672
745 71827467604063637297944
746 74644035894441963511212
747 77569111372432067672088
748 80606783511999258977100
749 83761327946241858475192
750 87037144126156813864704
751 90438830863445929119627
752 93971120649159692122112
753 97638959465072435264796
754 101447437589865555264672
755 105401873916068754179218
756 109507743062933655109920
757 113770764448900809156030
758 118196825521406735746892
759 122792075848499759280315
760 127562846266500323830976
761 132515748268790023043830
762 137657588862488998132560
763 142995475547621919130268
764 148536726663768290023536
765 154288982268807808242312
766 160260109745820766501376
767 166458320907477370176437
768 172892072622295613754884
769 179570190488510833210670
770 186501764227116960559888
771 193696278287782877033724
772 201163501743888100865988
773 208913626212792151838070
774 216957149975305493893008
775 225305023613421892011769
776 233968528063316134361716
777 242959428395573629934600
778 252289845496854829482548
779 261972418440761427572242
780 272020169478728123656256
781 282446675474013732785020
782 293265925867148664535960
783 304492503671198973643473
784 316141436061185954342982
785 328228385455811158877592
786 340769492363645744693952
787 353781577104999461282191
788 367281974530322860963240
789 381288746965930359453376
790 395820510401939672047872
791 410896659277200699862854
792 426537183715182694124628
793 442762906796803024411152
794 459595292402932818713888
795 477056695658954075734014
796 495170160921956484641888
797 513959686117872958591694
798 533450010389951290374432
799 553666893088328949972108
800 574636890573948297666338
801 596387650661537015363190
802 618947678049760580382124
803 642346645061887559771322
804 666615145148601022635968
805 691785020816265894375388
806 717889104623415247754880
807 744961565234624918739026
808 773037635305212705732476
809 802153976649393679315866
810 832348394380141538363160
811 863660222233685688430585
812 896130022302743282952064
813 929799991615670769502204
814 964713646771342377042384
815 1000916252930538274145285
816 1038454492629577357495228
817 1077376918403972556500152
818 1117733605025480110032588
819 1159576627043850632075334
820 1202959693658189189367584
821 1247938652531956760438260
822 1294571106474400885565736
823 1342916944957006252370434
824 1393037941744207548244288
825 1444998315616448035919424
826 1498864308051378981322928
827 1554704774739771577336179
828 1612590742378892310825600
829 1672596032652946954873310
830 1734796797159250754576768
831 1799272175614896927260149
832 1866103807893665153525564
833 1935376528315445203915793
834 2007177853727497920384816
835 2081598715833087154424076
836 2158732924204672823668560
837 2238677938713482412470220
838 2321534306314426575734228
839 2407406475749262746821722
840 2496402206893427881208320
841 2588633430022313130881533
842 2684215626458755109010844
843 2783268734815071585837234
844 2885916501626590240125012
845 2992287437111825321872356
846 3102514134422100616610544
847 3216734277598931544470418
848 3335089928012464417344108
849 3457728587339138960878792
850 3584802449702269691108234
851 3716469522644794185306750
852 3852892843423812781408768
853 3994241661113091592523188
854 4140690615439704955791904
855 4292420983319396530534347
856 4449619818557585791306028
857 4612481266298153889664274
858 4781205661842934459825200
859 4956000916681469900155810
860 5137081574612660317597824
861 5324670273220039662009912
862 5518996755406462560548728
863 5720299410387017683613233
864 5928824238672446843207352
865 6144826476870511772032524
866 6368569514076224586725116
867 6600326605002912899277743
868 6840379735657258243347872
869 7089021429564091534804648
870 7346553560521653958306656
871 7613289256939966780364848
872 7889551659386616032526288
873 8175675928328075795619366
874 8472007944088650634723952
875 8778906423568128860394318
876 9096741560146272588838920
877 9425897255249414164138472
878 9766769695640048851406056
879 10119769706020284702491652
880 10485321261050657311971872
881 10863863965510563000946134
882 11255851498292377517958738
883 11661754226989058018896732
884 12082057581009010984447268
885 12517264807829898094823040
886 12967895272276478820121840
887 13434487362068312444841542
888 13917596710197018018517264
889 14417799257805095480719504
890 14935689396490733747434592
891 15471883196986504290556731
892 16027016468109049824861808
893 16601748160161116991337712
894 17196758337130230602821800
895 17812751764216681114874378
896 18450455789769699451748168
897 19110624126848914785413648
898 19794034641268679390587004
899 20501493337632553493549328
900 21233832049736385723897186
901 21991912642076027681272966
902 22776624598737672180218216
903 23588889451969796177647037
904 24429658265565231482756412
905 25299916302710905512963660
906 26200680399740326191262992
907 27133003886130754951971507
908 28097973844377406061434284
909 29096716295699051489678742
910 30130393341656472475335520
911 31200208629856070404308898
912 32307404372805193028136464
913 33453267108671118936436300
914 34639124592735073855983180
915 35866351869073090755527854
916 37136368029839122874883460
917 38450642614586989090984088
918 39810692232481306437864696
919 41218087306878371940426986
920 42674448555432036639184640
921 44181454098498432377573964
922 45740835791972796708073668
923 47354386719081048474570964
924 49023957370653388944843360
925 50751463540917624802451052
926 52538882349786607432021056
927 54388260564376811578695189
928 56301710457759870316429424
929 58281418579098310226642830
930 60329641443187189842363600
931 62448714773330311346227666
932 64641049015876922854470124
933 66909139081259583984139688
934 69255559677613765350617752
935 71682975576766444926568371
936 74194136760914008436846172
937 76791889241792391367639846
938 79479170014281806670946304
939 82259018458508831058054922
940 85134571094146090319173120
941 88109073596798337105918284
942 91185875346672325385054760
943 94368442092287099033296149
944 97660350287104984432222032
945 101065300435385696913198216
946 104587111210294878727859376
947 108229733518597189218923927
948 111997244393695412433556128
949 115893861817834647860187348
950 119923938383474123586330216
951 124091976913758458617124245
952 128402623885587473635343864
953 132860685891307057207501790
954 137471122816821128748143604
955 142239065189770041282673582
956 147169807106025210609667856
957 152268824512063682246782980
958 157541767873201744285758376
959 162994481440447092456599970
960 168632995653865084477914784
961 174463547446902038332402051
962 180492572378338931242713200
963 186726726029938344216405177
964 193172875860527801229478212
965 199838123755836714984341016
966 206729797598367840671475168
967 213855475031467720209009250
968 221222974738792725382944790
969 228840381488005825377784396
970 236716037113826482977962224
971 244858566910277463493569040
972 253276870311528713531758188
973 261980148705340275473195444
974 270977895806172769249154392
975 280279926966396709977202678
976 289896369236450138694048600
977 299837692254521756536010110
978 310114697988893711868069984
979 320738553291167573665215662
980 331720779316341676101729840
981 343073285829247288248647244
982 354808360298379978779973896
983 366938704050061311272351561
984 379477421032577490133693080
985 392438055917693132433740604
986 405834582532253441761632904
987 419681444012065443427733742
988 433993540898797944466673776
989 448786273456927208345239744
990 464075529434528264503739712
991 479877728659972326261655767
992 496209810466050317903320008
993 513089280689425248489971564
994 530534198758471329930056872
995 548563227225143788591109322
996 567195618517962349952173984
997 586451267142982343046311172
998 606350696104507878874473660
999 626915111919251359364850657
1000 648166390708638202515967520