-1 1
0 0
1 1
2 3
3 3
4 4
5 7
6 7
7 9
8 15
9 16
10 20
11 29
12 32
13 40
14 55
15 61
16 74
17 99
18 111
19 134
20 170
21 192
22 230
23 285
24 323
25 382
26 466
27 530
28 622
29 746
30 848
31 988
32 1173
33 1331
34 1540
35 1810
36 2052
37 2363
38 2752
39 3114
40 3568
41 4129
42 4663
43 5318
44 6118
45 6895
46 7834
47 8963
48 10078
49 11410
50 12993
51 14579
52 16452
53 18655
54 20891
55 23506
56 26551
57 29673
58 33294
59 37480
60 41806
61 46784
62 52500
63 58450
64 65256
65 73015
66 81142
67 90384
68 100866
69 111901
70 124380
71 138465
72 153355
73 170118
74 188954
75 208932
76 231328
77 256402
78 283070
79 312854
80 346078
81 381498
82 420928
83 464772
84 511598
85 563563
86 621184
87 682818
88 751026
89 826455
90 907232
91 996406
92 1094782
93 1200231
94 1316372
95 1444208
96 1581345
97 1732068
98 1897619
99 2075315
100 2270232
101 2483915
102 2713372
103 2964602
104 3239522
105 3534829
106 3857610
107 4210237
108 4589080
109 5002513
110 5453468
111 5937999
112 6465976
113 7041025
114 7658900
115 8331232
116 9062508
117 9848186
118 10701984
119 11629439
120 12625772
121 13707141
122 14880366
123 16140501
124 17506588
125 18987014
126 20576751
127 22298236
128 24161771
129 26162400
130 28326540
131 30666824
132 33178550
133 35892844
134 38825172
135 41971321
136 45367960
137 49033986
138 52966034
139 57207282
140 61780774
141 66684415
142 71969058
143 77662789
144 83765306
145 90336480
146 97410490
147 104989548
148 113144136
149 121915777
150 131310037
151 141409906
152 152265792
153 163887677
154 176373250
155 189783596
156 204134488
157 219540914
158 236076812
159 253765343
160 272741860
161 293095788
162 314859679
163 338192844
164 363203246
165 389935317
166 418576580
167 449257229
168 482036519
169 517135166
170 554709996
171 594838745
172 637781164
173 683725869
174 732773502
175 785229739
176 841321198
177 901176689
178 965155880
179 1033530723
180 1106464630
181 1184380738
182 1267604958
183 1356343002
184 1451092606
185 1552243944
186 1660054220
187 1775108772
188 1897874180
189 2028670214
190 2168185084
191 2316976089
192 2475438708
193 2644381933
194 2824470754
195 3016192007
196 3220496388
197 3438176526
198 3669829294
199 3916571642
200 4179347293
201 4458885276
202 4756497488
203 5073306455
204 5410199594
205 5768717248
206 6150193236
207 6555704437
208 6987058904
209 7445839882
210 7933350368
211 8451711914
212 9002802032
213 9588193179
214 10210373830
215 10871568203
216 11573669319
217 12319595003
218 13111977658
219 13953090966
220 14846354756
221 15794881648
222 16801396730
223 17869906548
224 19004088033
225 20207200699
226 21483936562
227 22838635218
228 24275188012
229 25799087192
230 27415449860
231 29128913438
232 30945904006
233 32872450064
234 34914068694
235 37078275160
236 39372165584
237 41802292968
238 44377442128
239 47105958699
240 49995614194
241 53056672612
242 56298940783
243 59731621684
244 63366701744
245 67215695280
246 71289485208
247 75602062402
248 80166934820
249 84996954717
250 90108444520
251 95517238230
252 101238494106
253 107291245035
254 113694036840
255 120464725539
256 127625493142
257 135198044587
258 143203388744
259 151667364544
260 160615354544
261 170072048733
262 180067530084
263 190631459285
264 201792820498
265 213586619370
266 226047489692
267 239209420171
268 253113123304
269 267799009967
270 283306896188
271 299684106512
272 316977758110
273 335234446893
274 354509154042
275 374856776379
276 396331791046
277 418998040684
278 442919441124
279 468159623603
280 494792680752
281 522892977094
282 552534768188
283 583803996510
284 616787123710
285 651570726062
286 688254437996
287 726938717994
288 767724419777
289 810726989365
290 856063069480
291 903850046664
292 954221616716
293 1007313124371
294 1063261086295
295 1122220250746
296 1184347560762
297 1249801653173
298 1318761548786
299 1391409118088
300 1467928557668
301 1548526858919
302 1633414645148
303 1722805626725
304 1816939009688
305 1916058562913
306 2020412053972
307 2130275772202
308 2245931673178
309 2367666798474
310 2495800103136
311 2630657512411
312 2772571328446
313 2921909569052
314 3079048758750
315 3244373326885
316 3418307681588
317 3601286542736
318 3793754337634
319 3996200253594
320 4209125905634
321 4433044736101
322 4668520310366
323 4916131096308
324 5176469876240
325 5450185572480
326 5737944897724
327 6040431789597
328 6358393077980
329 6692596747096
330 7043831404284
331 7412956127410
332 7800855059764
333 8208436928009
334 8636689436340
335 9086629893538
336 9559304797792
337 10055849175843
338 10577432919705
339 11125260458373
340 11700635473672
341 12304902600002
342 12939447207564
343 13605765963247
344 14305403520192
345 15039952441302
346 15811130113248
347 16620710026335
348 17470521871452
349 18362535357384
350 19298785652269
351 20281373693536
352 21312557505530
353 22394671342435
354 23530126256308
355 24721509562368
356 25971497191774
357 27282854569754
358 28658544929930
359 30101634349667
360 31615292999276
361 33202913066746
362 34868005911002
363 36614203751823
364 38445388029620
365 40365578074424
366 42378933316850
367 44489892976672
368 46703055602782
369 49023181897779
370 51455346705648
371 54004808734155
372 56677014098692
373 59477761659671
374 62413062193724
375 65489142778718
376 68712626620076
377 72090380886746
378 75629522076983
379 79337611569422
380 83222491289348
381 87292290214590
382 91555636988986
383 96021482531578
384 100699107865231
385 105598355243624
386 110729436757954
387 116102943695804
388 121730097755444
389 127622544646549
390 133792365216196
391 140252348454370
392 147015769023679
393 154096400422639
394 161508811631130
395 169268127438642
396 177390043950638
397 185891150878334
398 194788673469552
399 204100490706054
400 213845485409122
401 224043266507133
402 234714190318484
403 245879740830180
404 257562230963134
405 269784827386675
406 282571963525942
407 295949018412580
408 309942345537760
409 324579721358460
410 339890000243780
411 355903147939550
412 372650728580852
413 390165534165339
414 408481623276026
415 427634849861282
416 447662465586934
417 468603164550387
418 490497657365264
419 513388244660780
420 537318868613986
421 562335736179895
422 588486861924184
423 615822127306243
424 644393957220058
425 674256830263839
426 705467346828666
427 738084963470322
428 772171468635534
429 807791060742331
430 845011145292080
431 883901773991401
432 924535734160326
433 966989413911416
434 1011342202525620
435 1057676592695196
436 1106079119554936
437 1156639720091932
438 1209451849915394
439 1264613502423794
440 1322226524957228
441 1382396751998023
442 1445235111296256
443 1510856894403895
444 1579381908447304
445 1650935676625712
446 1725648660704800
447 1803656433761977
448 1885100983115274
449 1970129882302412
450 2058896487497133
451 2151561351623588
452 2248291343301452
453 2349259869962412
454 2454648412669504
455 2564645589480543
456 2679447408658852
457 2799258934546319
458 2924293292784530
459 3054771957428165
460 3190926559125476
461 3332997829637289
462 3481235927120626
463 3635902398859786
464 3797269062551760
465 3965618374538192
466 4141245560404378
467 4324457430551464
468 4515572796731160
469 4714924785004039
470 4922859583198400
471 5139736911738924
472 5365932534737432
473 5601836937060308
474 5847855856151468
475 6104413008424534
476 6371948693817818
477 6650920396108076
478 6941805743301418
479 7245101037757721
480 7561321933372592
481 7891006650330526
482 8234714429145146
483 8593026294070372
484 8966548544396388
485 9355911131071737
486 9761768516802651
487 10184803468063670
488 10625725353360262
489 11085271111690302
490 11564209371612436
491 12063338670687139
492 12583488545331990
493 13125524005663842
494 13690343676218204
495 14278881021741009
496 14892109209119996
497 15531039170154871
498 16196720979503928
499 16890249137852798
500 17612760558303908
501 18365436114565554
502 19149506382608264
503 19966249553163881
504 20816993170317679
505 21703120372300513
506 22626067733670224
507 23587327216770084
508 24588452956010704
509 25631059034561131
510 26716821673701492
511 27847486609011644
512 29024866807841233
513 30250844924424760
514 31527381320840256
515 32856511733199660
516 34240350023550724
517 35681096903325108
518 37181037558105002
519 38742544730841427
520 40368088210841540
521 42060232429153585
522 43821639911512302
523 45655081601746106
524 47563434442328932
525 49549685239777710
526 51616941897736646
527 53768431000092046
528 56007502136329118
529 58337640126549611
530 60762462627783400
531 63285724972106489
532 65911333473504452
533 68643343081696307
534 71485962791695160
535 74443570130815120
536 77520708888481916
537 80722095162426971
538 84052633133336892
539 87517412903832807
540 91121717253697402
541 94871038819732802
542 98771078082410660
543 102827750910528744
544 107047207274877012
545 111435829427049972
546 116000240322772226
547 120747324010077472
548 125684224051528652
549 130818352925241482
550 136157414241532794
551 141709401467387845
552 147482608415058950
553 153485653455673763
554 159727478613312858
555 166217361263048204
556 172964940525941508
557 179980216809673295
558 187273564851153516
559 194855762494798262
560 202737990767381906
561 210931848415034610
562 219449383285841786
563 228303093038606650
564 237505941340263580
565 247071392094850944
566 257013410899327232
567 267346483085368350
568 278085651059785230
569 289246516635565125
570 300845261121852604
571 312898686066145024
572 325424216605524700
573 338439923830516681
574 351964569247091236
575 366017609311806369
576 380619220319442376
577 395790346933207908
578 411552708088411529
579 427928824680504273
580 444942072545209100
581 462616689938647204
582 480977808331923410
583 500051510259431874
584 519864838609322282
585 540445830863361329
586 561823582271736976
587 584028257216629218
588 607091127272048096
589 631044640207418589
590 655922433719168988
591 681759377724929466
592 708591649746377308
593 736456751339488061
594 765393555081283966
595 795442386935295748
596 826645045750811816
597 859044855448666287
598 892686755030672428
599 927617321562305705
600 963884828117292737
601 1001539342155967702
602 1040632752454755344
603 1081218833428076672
604 1123353352670350596
605 1167094102349921617
606 1212500970591544444
607 1259636059053269338
608 1308563719362667704
609 1359350632314530175
610 1412065936437785452
611 1466781270118576992
612 1523570859446466602
613 1582511658818587574
614 1643683399468019624
615 1707168686878429740
616 1773053154573592430
617 1841425519851351101
618 1912377691782081788
619 1986004939442400330
620 2062405955745549856
621 2141682977144193523
622 2223941967688531068
623 2309292691944151543
624 2397848847635391644
625 2489728267041183032
626 2585053000102229398
627 2683949461368595582
628 2786548650392564552
629 2892986246249473184
630 3003402770293441040
631 3117943827366565530
632 3236760213093122788
633 3360008094101670486
634 3487849272045352826
635 3620451305178709958
636 3757987707874206008
637 3900638239640787879
638 4048589042657647556
639 4202032862600004639
640 4361169365053960056
641 4526205290863839795
642 4697354700487494302
643 4874839320436641074
644 5058888718495548242
645 5249740574052028808
646 5447641057445878432
647 5652845027338516080
648 5865616329714196187
649 6086228213296887598
650 6314963551595183838
651 6552115173541266495
652 6797986318440943032
653 7052890885487865359
654 7317153799307821034
655 7591111508240256206
656 7875112264413102682
657 8169516527789640728
658 8474697511945373460
659 8791041498122294313
660 9118948281737788164
661 9458831770221241368
662 9811120334827297488
663 10176257303964122812
664 10554701618092999476
665 10946928223477327419
666 11353428617124507066
667 11774711564232508326
668 12211303538488636284
669 12663749323899093180
670 13132612800793155280
671 13618477437766888011
672 14121946956201174585
673 14643646191411017842
674 15184221641858805490
675 15744342202739763233
676 16324700109495672800
677 16926011550504591421
678 17549017476747255810
679 18194484635596417146
680 18863206253830215268
681 19556002931089310819
682 20273723772610724448
683 21017247150116016023
684 21787481687532798612
685 22585367502171536758
686 23411877051813345127
687 24268016222007475938
688 25154825686097808740
689 26073381847685181128
690 27024798039731378100
691 28010226014836347186
692 29030856993183882430
693 30087922984690344641
694 31182698422021963898
695 32316501325158350024
696 33490694758928991798
697 34706688622451234562
698 35965940942572299038
699 37269959480347637716
700 38620303691883805566
701 40018586164156019818
702 41466474385309812418
703 42965692893319509938
704 44518024869035240726
705 46125314086643874324
706 47789467268114679012
707 49512455849818607130
708 51296318131078151228
709 53143161854079319958
710 55055166162039465572
711 57034583965521550280
712 59083744769359526308
713 61205056842142487764
714 63401009821881046000
715 65674177813536386900
716 68027221791553142562
717 70462892468559662175
718 72984033689325538246
719 75593585090229484260
720 78294585256968290410
721 81090175443211206855
722 83983602513250024091
723 86978222417201776536
724 90077504265300281300
725 93285033582563045725
726 96604516132720561123
727 100039782382006459060
728 103594791097510838422
729 107273633554076324261
730 111080538424641734192
731 115019875757057044392
732 119096161601477155372
733 123314063367804543494
734 127678404219142639328
735 132194168160818728882
736 136866505909285999038
737 141700739744116909176
738 146702369103725386176
739 151877077014257730448
740 157230735446105684100
741 162769411465706076624
742 168499374277505451058
743 174427101135436674571
744 180559284104885512252
745 186902837775790841034
746 193464905784414294746
747 200252868244714791981
748 207274350196083283892
749 214537228796081061913
750 222049641486095303872
751 229819995243146122218
752 237856974510118104804
753 246169550166726498357
754 254766989661320553516
755 263658865751530653468
756 272855066358303545266
757 282365805660709253905
758 292201633726923231056
759 302373447336442219119
760 312892502128636222332
761 323770423211636174589
762 335019217045876435688
763 346651284745577464468
764 358679433761474192110
765 371116890927608487858
766 383977317024146280368
767 397274819639025319084
768 411023967489508625498
769 425239806364801486330
770 439937873281690251620
771 455134212202839132787
772 470845391488653859796
773 487088519472902717013
774 503881261711173724680
775 521241860083415294570
776 539189149927460929314
777 557742578963548858398
778 576922228202045604190
779 596748830785827877296
780 617243792750396619992
781 638429215905555030717
782 660327918551834760796
783 682963458250613830353
784 706360156864082577258
785 730543123326444640287
786 755538278614685494280
787 781372383148133820906
788 808073061812138582400
789 835668831337853622677
790 864189130281214190088
791 893664346515318027617
792 924125847246924078586
793 955606011814851030913
794 988138261887512212990
795 1021757094364917218982
796 1056498117258510468032
797 1092398082852378372203
798 1129494923762548149104
799 1167827792184281503380
800 1207437096299553231591
801 1248364539790532113501
802 1290653164766503741958
803 1334347391726491746464
804 1379493062851166865928
805 1426137488950085281443
806 1474329493316982023184
807 1524119459154187300229
808 1575559380911940396084
809 1628702912405141879451
810 1683605418756880140044
811 1740324032535441863638
812 1798917706535395765656
813 1859447270662285056738
814 1921975493309849637268
815 1986567139245479888705
816 2053289031896770823606
817 2122210120451665195206
818 2193401543328833903666
819 2266936696368896140301
820 2342891306183976475440
821 2421343499737734366624
822 2502373878989936907202
823 2586065601069611864698
824 2672504454537584339284
825 2761778941083076233521
826 2853980363146573044412
827 2949202907490180275977
828 3047543734599377001022
829 3149103074438268533586
830 3253984318010227954692
831 3362294115177241174872
832 3474142479291794083516
833 3589642887492527869475
834 3708912387718204582304
835 3832071713027513752860
836 3959245391442291520144
837 4090561863003470449957
838 4226153604663062670616
839 4366157250561357918531
840 4510713720048799838996
841 4659968354113826709463
842 4814071047060900295994
843 4973176386505616745090
844 5137443802388522029300
845 5307037711108404464595
846 5482127668588691952380
847 5662888533021415762381
848 5849500622605546276036
849 6042149882881489838961
850 6241028064451711227572
851 6446332895577679641978
852 6658268265086752965318
853 6877044416427302031974
854 7102878136490793883226
855 7335992955512293005626
856 7576619358939036446098
857 7824994993967108359163
858 8081364887984014575884
859 8345981679861379116350
860 8619105845829420193800
861 8901005938148454047601
862 9191958837579634414902
863 9492250000365959914403
864 9802173718970098035733
865 10122033397632861223901
866 10452141822387773273350
867 10792821445866318458067
868 11144404688023215617692
869 11507234231283746745641
870 11881663331595561992976
871 12268056146583942185114
872 12666788058118338417890
873 13078246011983428420238
874 13502828875927712154776
875 13940947792139320499158
876 14393026548119453005252
877 14859501967305200111537
878 15340824294166053771896
879 15837457599091604130261
880 16349880204505910586196
881 16878585105536807027147
882 17424080411978358864831
883 17986889813071023133054
884 18567553036957433591884
885 19166626333050314974356
886 19784682978931823106034
887 20422313782093805681872
888 21080127606335474482042
889 21758751924538590484806
890 22458833366499159186124
891 23181038293298163830081
892 23926053400038705088160
893 24694586313911802249883
894 25487366220830047856090
895 26305144522570644724374
896 27148695489582717055547
897 28018816944550195449620
898 28916330978773319316582
899 29842084664621075515708
900 30796950801098492693376
901 31781828694721196728622
902 32797644936946954537932
903 33845354217266589247503
904 34925940174284408889834
905 36040416243930225592937
906 37189826546075266398956
907 38375246812028793858802
908 39597785309839522360072
909 40858583810961407382893
910 42158818600916845451732
911 43499701488547505062651
912 44882480859823210611812
913 46308442779008326751194
914 47778912089320325836562
915 49295253561591909139577
916 50858873093913421105004
917 52471218911806956787955
918 54133782820121460963676
919 55848101509814473490936
920 57615757866454533917316
921 59438382334455684175875
922 61317654340411055877400
923 63255303719501403721426
924 65253112201963987291370
925 67312914963203386212964
926 69436602178514221195956
927 71626120642534976186354
928 73883475457243281938570
929 76210731726301707795473
930 78610016319175302880096
931 81083519709075173775954
932 83633497819213542770460
933 86262273944270689123412
934 88972240751388183452816
935 91765862291679583685432
936 94645676092824594690518
937 97614295337338540221060
938 100674411053835001089988
939 103828794395709468556620
940 107080299012131814705792
941 110431863434804327335883
942 113886513558981571923674
943 117447365223955636123374
944 121117626812405450228408
945 124900601951392282882396
946 128799692320541899406136
947 132818400482547499391713
948 136960332823290214896532
949 141229202607477243528345
950 145628833060450620697608
951 150163160568218956510924
952 154836238001996037518524
953 159652238073191181564124
954 164615456815912719837970
955 169730317203678268851632
956 175001372801330618852054
957 180433311554496467592570
958 186030959723719181734012
959 191799285859068968742743
960 197743404923124343536070
961 203868582569923301512335
962 210180239470230805973172
963 216683955796868653738285
964 223385475878205163230300
965 230290712904420703301228
966 237405753806458322319878
967 244736864316290003682788
968 252290494087097121616275
969 260073281999764867855102
970 268092061664890716038392
971 276353866992587581673132
972 284865937963316424639828
973 293635726609556944643218
974 302670903073964422026396
975 311979361884444938304114
976 321569228456608026399652
977 331448865682282666382944
978 341626880752107846612116
979 352112132223351931313744
980 362913737184339593430858
981 374041078671477996312548
982 385503813350779640015850
983 397311879307592291109168
984 409475504108930646090948
985 422005213151101729178790
986 434911838128288059767808
987 448206525795330832939288
988 461900747038254785947780
989 476006306079756774054759
990 490535350002215802189036
991 505500378602674890694424
992 520914254398160821599332
993 536790212973707427436308
994 553141873688504775526790
995 569983250549251237554844
996 587328763453400220998976
997 605193249818763705672352
998 623591976398807517476616
999 642540651497201570180389
1000 662055437599199704891552