-1 1
0 0
1 2
2 4
3 5
4 6
5 14
6 14
7 20
8 30
9 37
10 46
11 71
12 82
13 108
14 144
15 173
16 218
17 291
18 340
19 425
20 540
21 647
22 788
23 996
24 1170
25 1427
26 1744
27 2072
28 2476
29 3019
30 3536
31 4224
32 5058
33 5942
34 7008
35 8363
36 9734
37 11453
38 13512
39 15719
40 18340
41 21546
42 24908
43 28983
44 33774
45 38995
46 45086
47 52353
48 60130
49 69355
50 80034
51 91757
52 105296
53 121140
54 138320
55 158331
56 181292
57 206595
58 235540
59 268925
60 305440
61 347399
62 395138
63 447868
64 507722
65 576053
66 651062
67 736442
68 832932
69 939556
70 1059796
71 1195969
72 1345710
73 1514848
74 1704918
75 1914868
76 2150368
77 2415266
78 2706776
79 3033984
80 3399904
81 3803680
82 4254548
83 4758852
84 5313700
85 5933304
86 6623260
87 7383630
88 8229222
89 9170686
90 10205710
91 11356455
92 12633056
93 14037926
94 15594596
95 17320863
96 19216642
97 21316387
98 23638100
99 26188924
100 29006478
101 32120177
102 35535116
103 39304891
104 43460960
105 48019481
106 53040292
107 58571905
108 64630006
109 71297972
110 78629494
111 86657613
112 95477012
113 105167160
114 115763688
115 127396441
116 140155524
117 154103830
118 169390822
119 186145767
120 204440304
121 224475965
122 246402600
123 270334160
124 296505716
125 325126110
126 356329648
127 390428527
128 427668938
129 468250737
130 512542120
131 560878478
132 613499530
133 670888734
134 733445718
135 801512003
136 875662116
137 956431254
138 1044233092
139 1139814497
140 1243818200
141 1356815479
142 1479699458
143 1613317743
144 1758367466
145 1915998838
146 2087235956
147 2273018124
148 2474728368
149 2693699745
150 2931083410
151 3188645799
152 3468004688
153 3770682241
154 4098809936
155 4454472010
156 4839537328
157 5256709512
158 5708523880
159 6197416293
160 6726657064
161 7299483789
162 7918888762
163 8588994951
164 9313746660
165 10096996922
166 10943742436
167 11858980680
168 12847444644
169 13915398085
170 15068934740
171 16314087897
172 17658457632
173 19109712230
174 20675258052
175 22364574623
176 24187012658
177 26151935773
178 28270850790
179 30555455633
180 33017230508
181 35670464625
182 38529415488
183 41608495164
184 44925048232
185 48496818988
186 52341450776
187 56480393415
188 60935258324
189 65728058273
190 70884820336
191 76432314324
192 82397445314
193 88812278800
194 95709385690
195 103122152999
196 111089463886
197 119651493228
198 128848973860
199 138729646412
200 149342329982
201 160737331186
202 172972486672
203 186107784576
204 200204482972
205 215333368552
206 231567232920
207 248981412368
208 267661568400
209 287696832353
210 309178765568
211 332211897311
212 356904219752
213 383367902907
214 411729286820
215 442120176507
216 474676636494
217 509552404030
218 546906922836
219 586906299968
220 629736099500
221 675590344008
222 724670131068
223 777200674946
224 833416296164
225 893561711048
226 957908367106
227 1026740610953
228 1100354133168
229 1179077570446
230 1263253752130
231 1353241439456
232 1449436149380
233 1552252816802
234 1662124104208
235 1779527731285
236 1904963134940
237 2038953818824
238 2182073852112
239 2334926229325
240 2498141103904
241 2672410308648
242 2858458411460
243 3057045917975
244 3269002912024
245 3495202171714
246 3736557436532
247 3994066946587
248 4268777679260
249 4561789734786
250 4874298974154
251 5207563761175
252 5562903455084
253 5941753237731
254 6345620120132
255 6776088938774
256 7234876331258
257 7723789777360
258 8244726615552
259 8799742991354
260 9390999975136
261 10020771775551
262 10691513974268
263 11405813330876
264 12166387761546
265 12976172977617
266 13838256755440
267 14755890217392
268 15732573996340
269 16771997031984
270 17878038165266
271 19054874923841
272 20306903708908
273 21638755286123
274 23055403505274
275 24562091058068
276 26164333678700
277 27868056613171
278 29679498202196
279 31605231152563
280 33652299623544
281 35828129668335
282 38140537460692
283 40597900406617
284 43209041279064
285 45983257430400
286 48930493538640
287 52061234279477
288 55386518548466
289 58918153959218
290 62668578415456
291 66650900206579
292 70879115596068
293 75367981105544
294 80133036546390
295 85190873849758
296 90558972763816
297 96255755809091
298 102300862340432
299 108714997712213
300 115519969081718
301 122739022330419
302 130396648474720
303 138518658877714
304 147132530459472
305 156267229140109
306 165953263882816
307 176223109045431
308 187110978153340
309 198652926739849
310 210887287189826
311 223854464247142
312 237597014854320
313 252160177780622
314 267591611778466
315 283941536007019
316 301263277948772
317 319613039470348
318 339050012867880
319 359637045312983
320 381440339304720
321 404529644012085
322 428978946019908
323 454866205739232
324 482273523878258
325 511287975515153
326 542001272224864
327 574510022348234
328 608916602282164
329 645328865170243
330 683860377110864
331 724631465023301
332 767768842132400
333 813405961391247
334 861684115269888
335 912752121897765
336 966766657181188
337 1023893572453324
338 1084307488750300
339 1148192275790478
340 1215742441337592
341 1287162804739296
342 1362668960422728
343 1442488936320824
344 1526862767946544
345 1616043146272897
346 1710297174505744
347 1809906045956726
348 1915165686638964
349 2026388844837102
350 2143904663954580
351 2268059557193270
352 2399219430997882
353 2537769394307884
354 2684114644160056
355 2838683101567863
356 3001925013584552
357 3174314131886729
358 3356350529697566
359 3548560383513778
360 3751497187331076
361 3965745081600850
362 4191918531132630
363 4430663910008054
364 4682663074311072
365 4948633276809165
366 5229328824142368
367 5525545286274694
368 5838119319257340
369 6167930792364514
370 6515907324409394
371 6883024418841735
372 7270307715991120
373 7678838322619864
374 8109752879339808
375 8564246410118460
376 9043578088195924
377 9549071715882250
378 10082118773842040
379 10644185177285947
380 11236811729907888
381 11861617933847557
382 12520309326429762
383 13214678478660032
384 13946609109221730
385 14718084659709297
386 15531189334214812
387 16388113183667313
388 17291161451285032
389 18242756330943892
390 19245442499703440
391 20301898014883364
392 21414936215304198
393 22587512493625650
394 23822736212468184
395 25123873553982007
396 26494354937492462
397 27937788883320030
398 29457965154469576
399 31058863760951559
400 32744670168242702
401 34519779689572354
402 36388807402910080
403 38356605808705568
404 40428269728372188
405 42609148254439447
406 44904864178457576
407 47321320537159724
408 49864713836069916
409 52541556562230970
410 55358684538485104
411 58323272754928198
412 61442860207313848
413 64725359419708682
414 68179074033302942
415 71812727536167833
416 75635474013602832
417 79656919084850657
418 83887151682129192
419 88336757651774957
420 93016843093519168
421 97939071055757009
422 103115676940586360
423 108559496144436344
424 114284004743559512
425 120303338642639793
426 126632324474863908
427 133286526506835423
428 140282268375387152
429 147636669516715154
430 155367697284063804
431 163494193593621250
432 172035915747037426
433 181013596426356090
434 190448973987815980
435 200364840393780384
436 210785108006373992
437 221734846310032461
438 233240335731661100
439 245329144422045479
440 258030170047917460
441 271373702755998252
442 285391510806860752
443 300116890774620335
444 315584738363007756
445 331831646715478073
446 348895963580352570
447 366817873888521676
448 385639509572528468
449 405405017711770722
450 426160653534894194
451 447954906340139672
452 470838577122839520
453 494864886705049414
454 520089616597184548
455 546571200944021149
456 574370848440698544
457 603552703659469432
458 634183951803823126
459 666334960076980259
460 700079458378417540
461 735494662702978530
462 772661434676470940
463 811664488278915660
464 852592530428070340
465 895538445523061534
466 940599527243438404
467 987877643376971831
468 1037479444225373072
469 1089516627517550192
470 1144106126160449664
471 1201370348782974508
472 1261437477068681460
473 1324441684985776131
474 1390523410581753748
475 1459829695459933411
476 1532514434433818568
477 1608738688603365537
478 1688671066691511028
479 1772488015512102032
480 1860374173862587168
481 1952522807506635658
482 2049136139841991364
483 2150425758791191309
484 2256613105764813430
485 2367929859170577350
486 2484618394479168764
487 2606932341482083105
488 2735137020704250904
489 2869509971469564575
490 3010341578682236630
491 3157935577556555849
492 3312609650796138148
493 3474696142317489310
494 3644542631350898256
495 3822512616809538175
496 4008986320446730672
497 4204361349157623701
498 4409053468982448456
499 4623497518933220035
500 4848148163964192900
501 5083480780690512579
502 5329992486123540990
503 5588203004355581370
504 5858655668286821964
505 6141918589206449400
506 6438585641628344294
507 6749277608051209170
508 7074643496004656844
509 7415361669294263700
510 7772141142612140144
511 8145723077787382662
512 8536882068570983738
513 8946427618232684937
514 9375205824837598160
515 9824100854283079804
516 10294036611104847624
517 10785978651686575337
518 11300935856320819636
519 11839962333920528763
520 12404159577254535600
521 12994678376740065716
522 13612720973834167092
523 14259543506064362899
524 14936458178196269568
525 15644835714364751065
526 16386108112642179252
527 17161771126205945799
528 17973387035011749658
529 18822587768642741103
530 19711077719576720668
531 20640636896073589187
532 21613124440465465984
533 22630481839464237028
534 23694736486989723972
535 24808005670246295462
536 25972500207665336172
537 27190528497758568729
538 28464501009826057812
539 29796934429776606790
540 31190456234091727828
541 32647809774380293287
542 34171858972783461604
543 35765593515029721776
544 37432134578267159932
545 39174740175318057191
546 40996811019382178864
547 42901897005298817901
548 44893703258814939224
549 46976096789154471954
550 49153113789420443706
551 51428966513805368001
552 53808050788018726716
553 56294954264985914845
554 58894464204880896644
555 61611575987280418770
556 64451502408841284472
557 67419682518533943273
558 70521791223989394658
559 73763749799625001412
560 77151735876092385504
561 80692194319075474001
562 84391849061473948384
563 88257714436100905251
564 92297107448268818948
565 96517661140662124308
566 100927337399309227368
567 105534440840994761815
568 110347633858898867472
569 115375951136515239431
570 120628815308194962096
571 126116053944115704819
572 131847915941883181712
573 137835089234478347134
574 144088719906623985320
575 150620430755568860079
576 157442341251936293050
577 164567089108148355189
578 172007851228831888156
579 179778366265088930168
580 187892958883043194976
581 196366563466131161604
582 205214749528381871596
583 214453749080972231254
584 224100483371408870292
585 234172591578777813847
586 244688461597494293836
587 255667260263743270505
588 267128965674620803434
589 279094401883002810766
590 291585272978272144470
591 304624199554894675382
592 318234757727724554556
593 332441517627070811529
594 347270084455377193520
595 362747142436321730684
596 378900498195205060196
597 395759127056914936992
598 413353222452122128808
599 431714244879578220983
600 450874974006395540934
601 470869564293207166516
602 491733600140833408584
603 513504154604839340726
604 536219851906845455332
605 559920929632056234489
606 584649304773598998628
607 610448644076473898753
608 637364434054378810032
609 665444055373254839232
610 694736861876382578104
611 725294259498359808303
612 757169789898022760612
613 790419219340632918956
614 825100627486587619464
615 861274501528642762391
616 899003836007807648764
617 938354232817501461120
618 979394007000141419656
619 1022194298957794450662
620 1066829186912447698308
621 1113375805922017905466
622 1161914473848900930420
623 1212528817943838739110
624 1265305908544015376560
625 1320336400614679836279
626 1377714676027701673318
627 1437538993880894031429
628 1499911649335232632752
629 1564939133661619179493
630 1632732303029899840468
631 1703406556896531894432
632 1777082017805033721460
633 1853883721054594779801
634 1933941814810855293326
635 2017391762237862231767
636 2104374554377942636560
637 2195036934786118359747
638 2289531626497980352516
639 2388017571115064450781
640 2490660180698632593328
641 2597631592777335849230
642 2709110938574131915992
643 2825284625636882792216
644 2946346624039190408544
645 3072498767468082602964
646 3203951070030588097216
647 3340922047628407530348
648 3483639055597364803458
649 3632338644006749686117
650 3787266918171778354120
651 3948679917463045137116
652 4116844013415532392024
653 4292036314322814195842
654 4474545089849443446248
655 4664670217306603192811
656 4862723635303175144788
657 5069029819893501923650
658 5283926284430549985640
659 5507764088411704103621
660 5740908370968675515680
661 5983738910943578249014
662 6236650697164476331098
663 6500054526390045673157
664 6774377630381364450848
665 7060064315223977488900
666 7357576630995250849302
667 7667395074072325438216
668 7990019303303780650616
669 8325968890220929827584
670 8675784105048452330622
671 9040026719173249582871
672 9419280844984507924420
673 9814153815800962780022
674 10225277084389498914840
675 10653307163369256005911
676 11098926609626203614306
677 11562845030594197938712
678 12045800136564803918436
679 12548558842243483926858
680 13071918392966773422168
681 13616707542467140982631
682 14183787784752899965242
683 14774054614774949910233
684 15388438845788833622112
685 16027907987228548286283
686 16693467655000290129824
687 17386163045221426172991
688 18107080474508130630440
689 18857348957870431458957
690 19638141856441927242568
691 20450678599576313810758
692 21296226449244181714844
693 22176102342522783699013
694 23091674815932058823680
695 24044365978581316540929
696 25035653571332537417172
697 26067073117368716371786
698 27140220127600972652684
699 28256752402198803463152
700 29418392432784815368028
701 30626929867624843414816
702 31884224082758814563072
703 33192206865486376762609
704 34552885168553774899682
705 35968343982652500962569
706 37440749332726938743918
707 38972351355185772365060
708 40565487505579034052464
709 42222585904384422838234
710 43946168773506123407862
711 45738856018384499820086
712 47603368962373696960832
713 49542534184573602414480
714 51559287518306297788184
715 53656678219356204307537
716 55837873250103118483948
717 58106161742843011854963
718 60464959650361268394768
719 62917814528288619258877
720 65468410515225555400256
721 68120573521526740628010
722 70878276565588522971908
723 73745645330609549888114
724 76726963951597889533496
725 79826680969668939873554
726 83049415529763079104542
727 86399963834805127648210
728 89883305786962668905728
729 93504611900123722720771
730 97269250495441701120232
731 101182795108587995246350
732 105251032196540487064776
733 109479969159493206281604
734 113875842599363900856322
735 118445126911873549726257
736 123194543226564756303092
737 128131068613983267916238
738 133261945661348288154676
739 138594692435382509589335
740 144137112743503761295668
741 149897306805172725042981
742 155883682350822670597048
743 162104966057067459809894
744 168570215435089394081664
745 175288831194595070122666
746 182270569983065646734476
747 189525557629189361639364
748 197064302911617200298004
749 204897711749993668176944
750 213037101953144231827896
751 221494218551288329251264
752 230281249599217616278804
753 239410842599048840365007
754 248896121568203912210592
755 258750704636500557382749
756 268988722327997511258892
757 279624836559867000091923
758 290674260231022495190610
759 302152777571873436518155
760 314076765286338766879200
761 326463214355500021595009
762 339329752682522730428068
763 352694668617639003988523
764 366576935220167808455552
765 380996235455227438510567
766 395972988362926152105054
767 411528376053366012475484
768 427684371734807808035714
769 444463768821660238834754
770 461890210961865368355844
771 479988223211696531027450
772 498783244403834883061932
773 518301660544365999576788
774 538570839478094140531932
775 559619166878340849859704
776 581476083381634663872048
777 604172123130398963655378
778 627738953779315214557950
779 652209417781564836714092
780 677617575231423084350848
781 703998748330850524777076
782 731389567279465799206884
783 759828017891584743638184
784 789353491007914395389970
785 820006833496840107662050
786 851830401164692306380648
787 884868113656506958549433
788 919165511123702244851964
789 954769813009306457302816
790 991729979032784489892804
791 1030096772146248759023772
792 1069922823831139297892790
793 1111262701833645984746303
794 1154172980090341167808416
795 1198712311249012964512803
796 1244941501884294739305112
797 1292923590154807595983464
798 1342723926328491833661168
799 1394410256294655103063149
800 1448052807787239574849678
801 1503724379787266892488580
802 1561500435225349806588512
803 1621459196704015875233530
804 1683681745733299888425368
805 1748252125622615131303452
806 1815257447724459300001256
807 1884788001570909001393346
808 1956937369049624070982332
809 2031802542310306304431318
810 2109484045972557812065300
811 2190086063807743453780449
812 2273716569559583979288968
813 2360487462529111188319456
814 2450514708102037583934334
815 2543918482879006386851110
816 2640823325069643158626876
817 2741358290358788240006802
818 2845657112877110969649776
819 2953858372000037213989969
820 3066105665191033593257104
821 3182547786517811239473431
822 3303338911606921966008124
823 3428638789288371213518165
824 3558612939528528184126296
825 3693432858489464467453537
826 3833276230976818131396676
827 3978327149871804575082288
828 4128776343434426254543792
829 4284821410781778529957433
830 4446667065104866554982924
831 4614525385594837383844277
832 4788616078396535344277104
833 4969166746151577437631709
834 5156413167159488951734712
835 5350599584523976727967452
836 5551979004812584063784800
837 5760813507355119521389895
838 5977374564566382647091576
839 6201943372822246923365667
840 6434811195082425724791840
841 6676279715703353564054270
842 6926661406934830247656872
843 7186279908405719044775601
844 7455470420066111029773768
845 7734580108083210322918748
846 8023968525076337872871876
847 8324008045226749660040215
848 8635084313723078211442384
849 8957596712057347776240353
850 9291958839738119297049652
851 9638599011888929199869734
852 9997960774341476022978972
853 10370503436870719069076375
854 10756702624003179313773552
855 11157050845157936531586156
856 11572058084806871720034640
857 12002252412097753652417136
858 12448180611811202233957304
859 12910408837433337603326777
860 13389523285751242070508920
861 13886130895016197027117757
862 14400860067506418332058324
863 14934361415915189937141644
864 15487308535741061422409002
865 16060398804624523422363046
866 16654354208022103810373514
867 17269922193596363934743629
868 17907876555329094814586056
869 18569018346775777305452874
870 19254176825995369039738944
871 19964210433296157026392868
872 20700007801183764210411512
873 21462488799279764530675271
874 22252605615430471918472224
875 23071343872429802906959760
876 23919723783308541915862228
877 24798801346567725079542038
878 25709669580752953010985300
879 26653459801594452117204324
880 27631342943188972884478816
881 28644530922671738126775914
882 29694278051820664310282724
883 30781882497256540832081226
884 31908687788667625918291104
885 33076084378817969753369452
886 34285511257125440501375814
887 35538457616306488247765939
888 36836464576104111971621148
889 38181126966107704000246093
890 39574095167152507042400506
891 41017077015684486828780739
892 42511839773250800626065012
893 44060212160693758048772489
894 45664086461738375677584940
895 47325420698398264641498543
896 49046240877782846792501524
897 50828643315426609647776621
898 52674797037752269539378262
899 54586946263368003629810128
900 56567412968679688424723998
901 58618599540744507976929429
902 60742991517090546989261252
903 62943160418485824790669851
904 65221766677813634975615560
905 67581562664929616280457514
906 70025395813910607659307364
907 72556211856226229452284598
908 75177058159758619523765968
909 77891087180667360406851419
910 80701560031913767218114480
911 83611850168562543254616370
912 86625447197363216394396912
913 89745960814870714175671146
914 92977124874306340755212812
915 96322801589347840139893995
916 99786985879455144599226952
917 103373809857177330821247742
918 107087547466228379334724904
919 110932619275468407098448454
920 114913597429361948891129996
921 119035210764503954021857369
922 123302350097775026979551844
923 127720073687005507618092691
924 132293612874449042843477908
925 137028377919258584806260764
926 141929964020025039721319374
927 147004157538619787245787090
928 152256942432052865741739204
929 157694506893793521573061846
930 163323250216636256073323432
931 169149789884576559332190951
932 175180968895392724025151076
933 181423863327119409417581964
934 187885790156509722853540862
935 194574315331664984532771441
936 201497262113016483319453920
937 208662719691652841300483592
938 216079052087508691814802756
939 223754907342892428607982344
940 231699227021116647808490528
941 239921256013347698214801822
942 248430552670336941249071860
943 257236999269866673386999476
944 266350812823472259690684432
945 275782556240621691844076885
946 285543149862121438741597612
947 295643883367054994640252461
948 306096428072841440826367052
949 316912849641458158240792590
950 328105621196714371682039544
951 339687636873947152446348530
952 351672225816320044377915240
953 364073166623531693886106652
954 376904702275975148069355876
955 390181555550049128190876969
956 403918944931176413171230560
957 418132601049667997515808838
958 432838783656511507292516920
959 448054299146773842986894655
960 463796518657738234373230208
961 480083396760668860626085932
962 496933490754847545149169048
963 514365980593471227544573101
964 532400689461970895804935260
965 551058105018791659589422725
966 570359401330575574031051080
967 590326461524472948565276579
968 610981901168830843956828174
969 632349092417106707843948460
970 654452188939749725362724246
971 677316151657009787231835847
972 700966775310316335331680910
973 725430715899552909019149007
974 750735519000708573339264858
975 776909649004972383249156514
976 803982519309033465134686312
977 831984523473162178839272940
978 860947067391457446335879144
979 890902602507105131908317618
980 921884660091126350234050348
981 953927886633036691364029687
982 987068080379202419893727400
983 1021342229039930548312381283
984 1056788548717656228573565380
985 1093446524095691273138247916
986 1131356949910940646686938392
987 1170561973767710197927890151
988 1211105140335616095043371968
989 1253031436958121503983690078
990 1296387340733507275844829910
991 1341220867115675188675418012
992 1387581620064247537450351208
993 1435520843811386194861120049
994 1485091476297002631074572828
995 1536348204305618444927801156
996 1589347520377863688060876536
997 1644147781553519743862601834
998 1700809269982995489736115040
999 1759394255486854045212167106
1000 1819967060125440435475925884