1 0
2 1
3 0
4 3
5 1
6 5
7 4
8 11
9 8
10 19
11 19
12 35
13 36
14 59
15 65
16 104
17 115
18 168
19 196
20 276
21 321
22 440
23 521
24 694
25 821
26 1072
27 1277
28 1644
29 1957
30 2477
31 2959
32 3705
33 4411
34 5472
35 6516
36 8014
37 9524
38 11620
39 13789
40 16724
41 19798
42 23860
43 28202
44 33815
45 39864
46 47579
47 55979
48 66520
49 78080
50 92416
51 108250
52 127675
53 149213
54 175385
55 204557
56 239701
57 278963
58 325948
59 378588
60 441148
61 511373
62 594353
63 687650
64 797346
65 920763
66 1065203
67 1227892
68 1417467
69 1631053
70 1879038
71 2158525
72 2481869
73 2846299
74 3266597
75 3740276
76 4285016
77 4898738
78 5602643
79 6395504
80 7302598
81 8323819
82 9489579
83 10801383
84 12295614
85 13976094
86 15886483
87 18033708
88 20470186
89 23206863
90 26306763
91 29786367
92 33721250
93 38134907
94 43118388
95 48704233
96 55001877
97 62055530
98 69996893
99 78885015
100 88878433
101 100054741
102 112604904
103 126630198
104 142360365
105 159926035
106 179604187
107 201562031
108 226133017
109 253530002
110 284154572
111 318276020
112 356377987
113 398799109
114 446121875
115 498770735
116 557446599
117 622678850
118 695311417
119 776002129
120 865766161
121 965418452
122 1076179943
123 1199056959
124 1335517374
125 1486799875
126 1654668533
127 1840644761
128 2046846890
129 2275138382
130 2528062705
131 2807896990
132 3117692546
133 3460226387
134 3839157245
135 4257864622
136 4720733074
137 5231866806
138 5796516967
139 6419659887
140 7107579562
141 7866298482
142 8703333077
143 9625959815
144 10643161975
145 11763717800
146 12998356555
147 14357651971
148 15854409793
149 17501347330
150 19313737853
151 21306857019
152 23498906707
153 25908209911
154 28556444896
155 31465561494
156 34661357737
157 38170096338
158 42022455820
159 46249821061
160 50888647836
161 55976397462
162 61556359016
163 67673198261
164 74378278765
165 81724796491
166 89773653301
167 98588136861
168 108240403191
169 118805669525
170 130369363403
171 143020789730
172 156861015128
173 171995965299
174 188545121991
175 206634007490
176 226403769556
177 248003011581
178 271598359542
179 297365581502
180 325501236932
181 356213040635
182 389732698717
183 426305464358
184 466204283116
185 509718481511
186 557169359372
187 608897955146
188 665282223641
189 726723826107
190 793667060967
191 866584608353
192 945998395489
193 1032464242787
194 1126594855699
195 1229043312358
196 1340528404678
197 1461816902112
198 1593751491319
199 1737231759094
200 1893244988571
201 2062845813817
202 2247190178847
203 2447513597470
204 2665168609955
205 2901601611251
206 3158394164409
207 3437238358875
208 3739982393957
209 4068604429659
210 4425262902890
211 4812268855257
212 5232141472366
213 5687578897080
214 6181519564549
215 6717111497843
216 7297780070247
217 7927195835036
218 8609349401412
219 9348517867161
220 10149347592868
221 11016819327542
222 11956339760889
223 12973705485710
224 14075204278626
225 15267578101800
226 16558135209191
227 17954712407584
228 19465799206131
229 21100499666001
230 22868669930969
231 24780880059694
232 26848566461345
233 29083994179304
234 31500425943127
235 34112085499624
236 36934345155190
237 39983690890638
238 43277930540258
239 46836161522195
240 50679002049587
241 54828562533215
242 59308702479540
243 64145006802052
244 69365071420477
245 74998485921645
246 81077151249223
247 87635270444813
248 94709702177870
249 102339961619834
250 110568614085911
251 119441288378333
252 129007115325778
253 139318756405430
254 150432892515433
255 162410271125204
256 175316251326339
257 189220873257957
258 204199466240166
259 220332744865051
260 237707487790756
261 256416665606160
262 276560198888665
263 298245123658646
264 321586438362344
265 346707313731493
266 373740039504575
267 402826286516112
268 434118165386856
269 467778549804951
270 503982260957377
271 542916462359744
272 584781985435333
273 629793807810088
274 678182537482897
275 730194988134002
276 786095841499883
277 846168335344282
278 910716126039534
279 980064107067805
280 1054560496658943
281 1134577807186305
282 1220515185845170
283 1312799558273260
284 1411888253648267
285 1518270349186015
286 1632469615110454
287 1755046090267087
288 1886599386844897
289 2027770531716523
290 2179245675698089
291 2341758239965589
292 2516093080367018
293 2703088983592233
294 2903643343398303
295 3118715057410753
296 3349329779090194
297 3596583272996017
298 3861647314482269
299 4145773568880775
300 4450300219883084
301 4776656447111037
302 5126369874126440
303 5501071728756954
304 5902505213167619
305 6332531442430746
306 6793138851876621
307 7286450022171634
308 7814732253307557
309 8380405398775625
310 8986053751853866
311 9634435027312491
312 10328493723704124
313 11071371409393199
314 11866421744682382
315 12717222249286565
316 13627591191072258
317 14601601034906485
318 15643597430362734
319 16758214567843186
320 17950396526023137
321 19225414790240392
322 20588892252859323
323 22046823181264406
324 23605600200339010
325 25272037034390375
326 27053398841145662
327 28957428093063240
328 30992378677771024
329 33167045330309042
330 35490801965729142
331 37973635125955966
332 40626187066827975
333 43459793741635519
334 46486533228914942
335 49719268839748544
336 53171703543916114
337 56858428861784637
338 60794986026018874
339 64997921401032452
340 69484855207141630
341 74274544302483125
342 79386959396576776
343 84843356133145108
344 90666361831586606
345 96880055924904277
346 103510067393209946
347 110583665740039276
348 118129870421967010
349 126179553692101065
350 134765563486086082
351 143922839623751449
352 153688551787133713
353 164102230752524178
354 175205923291742741
355 187044340310258059
356 199665030720938749
357 213118548591134429
358 227458648282722141
359 242742472964321462
360 259030773583958383
361 276388121386939640
362 294883153591350793
363 314588812868982031
364 335582622934070992
365 357946958298361746
366 381769353362704038
367 407142806153157434
368 434166124927475426
369 462944270040730053
370 493588742551293324
371 526217968856399506
372 560957736308488514
373 597941625811652128
374 637311500045522817
375 679217989826651229
376 723821041191969809
377 771290462012592013
378 821806534918140183
379 875560631413600338
380 932755898437556130
381 993607948082970915
382 1058345626488425871
383 1127211788210133450
384 1200464157153439820
385 1278376195699871364
386 1361238068508219068
387 1449357617675977648
388 1543061441490101609
389 1642695988210917329
390 1748628763244110734
391 1861249555593715900
392 1980971788474331333
393 2108233894102722319
394 2243500824493114841
395 2387265592061687868
396 2540050959264110915
397 2702411164497681098
398 2874933811370728060
399 3058241801621938298
400 3252995447182095770
401 3459894634314896112
402 3679681184266162479
403 3913141275594967839
404 4161108082132438818
405 4424464483544331033
406 4704146012576725420
407 5001143887304010234
408 5316508303253694833
409 5651351824588934102
410 6006853060719031327
411 6384260457879710172
412 6784896404296428981
413 7210161468305229888
414 7661538981087384404
415 8140599772672260186
416 8649007286756652496
417 9188522871701544650
418 9761011488051337575
419 10368447618039181094
420 11012921633190255534
421 11696646392959497312
422 12421964347311476498
423 13191354902999436558
424 14007442344345738984
425 14873004054416803367
426 15790979346466000242
427 16764478636961210249
428 17796793290392701888
429 18891405851866611621
430 20052001019336786924
431 21282477055399531929
432 22586958013592778275
433 23969806462246182264
434 25435637105434493735
435 26989330966382424648
436 28636050559111134838
437 30381255695122042864
438 32230720378889692161
439 34190550419524643940
440 36267202242217445538
441 38467502506487484786
442 40798669046672527012
443 43268332720409647368
444 45884560714499056776
445 48655880871668079120
446 51591307623853286897
447 54700369072307595860
448 57993135838807719362
449 61480251204052503203
450 65172963198793435131
451 69083158138546273507
452 73223396311476027313
453 77606949284029468201
454 82247839580940235359
455 87160882176850645098
456 92361728606412115350
457 97866913101714517191
458 103693901617566015158
459 109861143124020181751
460 116388124084002064789
461 123295425464908638627
462 130604783263309694640
463 138339151860042261145
464 146522771250320301897
465 155181237433534302257
466 164341577077386890725
467 174032325707395886913
468 184283610611308151055
469 195127237674820489432
470 206596783418267237784
471 218727691415096953612
472 231557374447521566175
473 245125321543691605933
474 259473211343540210977
475 274645030900354059594
476 290687201463448873469
477 307648710310982737816
478 325581250283481620063
479 344539366048444106207
480 364580608859299165594
481 385765698799899007428
482 408158696398576910829
483 431827182563405223622
484 456842448852113353059
485 483279696988547076276
486 511218249777911431405
487 540741772292913868614
488 571938505631891393081
489 604901512081506707773
490 639728934144775935709
491 676524266227959996276
492 715396641618460108039
493 756461133508977919094
494 799839072884053123098
495 845658381987109608537
496 894053926381682216851
497 945167884289343681116
498 999150136430238832407
499 1056158675015098118382
500 1116360035342694338396
501 1179929748620456526090
502 1247052819707342951093
503 1317924228368569645981
504 1392749458004904727969
505 1471745050421694381159
506 1555139190883869751773
507 1643172322002102921499
508 1736097791001442629033
509 1834182528902828011304
510 1937707766497200991061
511 2046969785633988189711
512 2162280711057246257628
513 2283969341309805561170
514 2412382024319519172227
515 2547883576194828638278
516 2690858249254067685091
517 2841710747832186321274
518 3000867298331531533218
519 3168776772087884992491
520 3345911867995149844841
521 3532770353500017652749
522 3729876371424193826020
523 3937781811280026627782
524 4157067753091822839939
525 4388345982459591304947
526 4632260585476103104476
527 4889489622323444759289
528 5160746888806171016148
529 5446783764757637945870
530 5748391159274418944358
531 6066401551849480356835
532 6401691140112746535498
533 6755182093410471015855
534 7127844923746462028059
535 7520700973507266008533
536 7934825032374580317541
537 8371348083071323956128
538 8831460189296259351713
539 9316413525755561552880
540 9827525564675376273438
541 10366182419007841753829
542 10933842357827874012144
543 11532039494484348929073
544 12162387664207560946614
545 12826584492140235726702
546 13526415669797759467212
547 14263759441387036101360
548 15040591319401119006725
549 15858989031446316824090
550 16721137719247393771916
551 17629335392387257409848
552 18585998659382378786898
553 19593668739330475367496
554 20655017778525435873810
555 21772855476045490988437
556 22950136044653441897972
557 24189965511883450011531
558 25495609389760222481875
559 26870500719003331422435
560 28318248518446870674095
561 29842646646626986902923
562 31447683108744666057635
563 33137549817190563206070
564 34916652841526136872088
565 36789623157490803836363
566 38761327933844230684608
567 40836882368160756038635
568 43021662113547856940039
569 45321316309134373202814
570 47741781259732931878117
571 50289294779451268289252
572 52970411248382755412827
573 55792017399300798676396
574 58761348887532385576335
575 61886007663328969644804
576 65173980204302194837975
577 68633656629904565319916
578 72273850760292504845275
579 76103821144509531461202
580 80133293125507929616218
581 84372481970229729361286
582 88832117137893607545704
583 93523467718349755486195
584 98458369119764234723813
585 103649251041530131633729
586 109109166818311563022595
587 114851824175586263892374
588 120891617489813817747672
589 127243661598539756731158
590 133923827261410912691103
591 140948778322879868289530
592 148336010686104974577774
593 156103893154865841590503
594 164271710262275064085245
595 172859707149778801456683
596 181889136625310116384643
597 191382308471452639156489
598 201362641143441996134207
599 211854715935986885264035
600 222884333770659155878860
601 234478574691791960738598
602 246665860235600327504445
603 259476018770333695775231
604 272940353986275138818278
605 287091716644268261871289
606 301964579776922818844983
607 317595117463148346758570
608 334021287386848389238854
609 351282917313594635872094
610 369421795714259306082068
611 388481766683911122512235
612 408508829404692852340945
613 429551242316912674044521
614 451659632268541741202181
615 474887108824854470264319
616 499289384031766489059461
617 524924897833837092810497
618 551854949465908944499085
619 580143835040470633110955
620 609858991677369391108080
621 641071148421144122482761
622 673854484322695012091143
623 708286793956003325020313
624 744449660779356222148010
625 782428638639703407232607
626 822313441865222355066795
627 864198144275331938347815
628 908181387591990989650286
629 954366599615084941433357
630 1002862222687911690500123
631 1053781952852356753091026
632 1107244990265659231124558
633 1163376301318667209422896
634 1222306893077417705785355
635 1284174100532094429055828
636 1349121887329531608245440
637 1417301160521671599165285
638 1488870100065264310240860
639 1563994503658155971322810
640 1642848147711782841128502
641 1725613165103162187124349
642 1812480440575989523126257
643 1903650024497541475876754
644 1999331565917150136321682
645 2099744765702315662615494
646 2205119850781084539424968
647 2315698070342629985132090
648 2431732215114816671455577
649 2553487160653648577047140
650 2681240435861469376664149
651 2815282817759511860833438
652 2955918953838380570233558
653 3103468013111196275260744
654 3258264367309084404912114
655 3420658303452063700830247
656 3591016769361318930268477
657 3769724153464265427094019
658 3957183100595786828733168
659 4153815365276329815478114
660 4360062704319700013569355
661 4576387810392423524353959
662 4803275288540099021664907
663 5041232677456756393725124
664 5290791517689489596615711
665 5552508468722661122560248
666 5826966477326293303159659
667 6114775999296615827501094
668 6416576277182586552403499
669 6733036676326788444734270
670 7064858082042041832070048
671 7412774360470819528590551
672 7777553886196238690005408
673 8160001139390272686537109
674 8560958375837032603771075
675 8981307372876949088425754
676 9421971254902298202806591
677 9883916401733633942256176
678 10368154443825721870766237
679 10875744347941891776325046
680 11407794597591323713279217
681 11965465472205422807746021
682 12549971429723888212496874
683 13162583596934204552090815
684 13804632372644031007011720
685 14477510148430790035677111
686 15182674152492408860109629
687 15921649421779985089601851
688 16696031908419486992237992
689 17507491726078768071670749
690 18357776542812176384600075
691 19248715126556998905018923
692 20182221050384819824200673
693 21160296564246152631950146
694 22185036640931775575694722
695 23258633203603431780831635
696 24383379543291483900823120
697 25561674934381035358817576
698 26796029457216695336451104
699 28089069036575640425847518
700 29443540705935173547992275
701 30862318107077008028659271
702 32348407235819370473979612
703 33904952444281741947545349
704 35535242711412985525881423
705 37242718193126345662129300
706 39030977064792873021759517
707 40903782668458071513825001
708 42865070978642207136517539
709 44918958400200160869987533
710 47069749913305743455792276
711 49321947580244947084416266
712 51680259430391266998057153
713 54149608739362054124412524
714 56735143720149813677168753
715 59442247643656885156493439
716 62276549407970337522897374
717 65243934575359840204539196
718 68350556898010772864650377
719 71602850353165203062315721
720 75007541710502177338990527
721 78571663654266959187990618
722 82302568484955778246906572
723 86207942425062431602884164
724 90295820555837558457185239
725 94574602411736960182064767
726 99053068261837486867408499
727 103740396107254980073466282
728 108646179426369432376004060
729 113780445699454056867592285
730 119153675747255794810191224
731 124776823917907579092584253
732 130661339159696163831241599
733 136819187017089666746570655
734 143262872590778528033817896
735 150005464502418416272418609
736 157060619908333622844291123
737 164442610606436458041737149
738 172166350284424075743657792
739 180247422957381699408711879
740 188702112646979625234980603
741 197547434354598774491805522
742 206801166385048270439718536
743 216481884077775957787967300
744 226608995007090917427641518
745 237202775713255715992248602
746 248284410031234245117912804
747 259876029084333227388082481
748 272000753015235637512445834
749 284682734527503522291103500
750 297947204316243652260199155
751 311820518467350454195306960
752 326330207910737891226503083
753 341505030013850929625307209
754 357375022408153111888401646
755 373971559142341384523381982
756 391327409262883320510391588
757 409476797923721520104686097
758 428455470134303731603283279
759 448300757256563055012351455
760 469051646369290148207052428
761 490748852620044472930732022
762 513434894693109568086793032
763 537154173523966994736458516
764 561953054399701291436418508
765 587879952587010026174202126
766 614985422639052787782359782
767 643322251534956851141758960
768 672945555816024587174193215
769 703912882885626491056632827
770 736284316650707578003868592
771 770122587686164323968462797
772 805493188115062409392250996
773 842464491401424484231801622
774 881107877264856119138280519
775 921497861930508966897650484
776 963712233941305930695400886
777 1007832195764102015792007802
778 1053942511435832729230940814
779 1102131660501018978967562257
780 1152491998507398607844962787
781 1205119924332394580545595795
782 1260116054629629972474405333
783 1317585405691321951144519813
784 1377637583040067753323090814
785 1440386979070904389686027965
786 1505952979083473272501539239
787 1574460176052306497672815130
788 1646038594503564306231741224
789 1720823923875631772572502374
790 1798957761762760795853923135
791 1880587867450997711016876861
792 1965868426178989793957461907
793 2054960324567383715245385805
794 2148031437685574959988496428
795 2245256928236850049862486873
796 2346819558369829476324615653
797 2452910014637670908468766230
798 2563727246655315255318037140
799 2679478820019993426123244822
800 2800381284091138897866440913
801 2926660555242294557490348427
802 3058552316230792385780146229
803 3196302432349070982673074696
804 3340167385057119603995761597
805 3490414723815413212435614722
806 3647323536875944104854372511
807 3811184941810779505466130395
808 3982302596598630868938622346
809 4160993232113864307165324253
810 4347587206906466286778181112
811 4542429085187728425085143895
812 4745878238983757745485848547
813 4958309475447676092577677004
814 5180113690372219755175706507
815 5411698548975933705036020509
816 5653489195090772988404272094
817 5905928989913369602619653033
818 6169480281540898467375910805
819 6444625206550140250035363130
820 6731866524941379563149184500
821 7031728489809936528936467117
822 7344757753175867938474111907
823 7671524309447328739557678338
824 8012622478065877753925341826
825 8368671926931085309404322463
826 8740318738280033451690808677
827 9128236518750843200057140064
828 9533127555443450510374773700
829 9955724019849245745905647793
830 10396789221611579064695400908
831 10857118914142786787156885663
832 11337542654220562230064676464
833 11838925217755850132106626321
834 12362168074028910280335677689
835 12908210920765733948709388923
836 13478033282539318204006211305
837 14072656175062541627480953701
838 14693143838060160984915962394
839 15340605539496947277191091860
840 16016197454068855660814978906
841 16721124618961488016671284278
842 17456642970019778059138208524
843 18224061461578712149605672299
844 19024744273355113357369276468
845 19860113107915624564548474702
846 20731649582397589558172484079
847 21640897718284626788209084731
848 22589466533212469536969567242
849 23579032738916552884769133768
850 24611343549619756342195494594
851 25688219605306317642553761471
852 26811558014529015998945093451
853 27983335521556989585335920323
854 29205611802887870871757957597
855 30480532898321885857542512935
856 31810334782028282580975112340
857 33197347079223230969832465267
858 34643996934328709260986974368
859 36152813036686690045121312924
860 37726429810172315054420726676
861 39367591773271869072269991548
862 41079158076481194337163804255
863 42864107224121036582705797547
864 44725541987977662597849565279
865 46666694520438183262267239921
866 48690931675125564484510733173
867 50801760543321281900670787759
868 53002834214824633562504361265
869 55297957772204341123971868575
870 57691094527786586371560783894
871 60186372513055790871670370923
872 62788091230562517186102042929
873 65500728678792626422598057680
874 68328948660901707796644898165
875 71277608388608358673281891311
876 74351766393024012160570557282
877 77556690754618762314523315596
878 80897867665043605271824552291
879 84381010333986027381770873680
880 88012068254796499685241527105
881 91797236843117480216606935209
882 95742967463349837634036775547
883 99855977858326166090851623010
884 104143262998209710185630263729
885 108612106365215906148002689306
886 113270091691452231042560985663
887 118125115167797535986446760187
888 123185398142493926724998052938
889 128459500328800670307395801567
890 133956333541868745813263220843
891 139685175985726026658192224020
892 145655687112133829720466376360
893 151877923073866223867140392065
894 158362352795900532829985232289
895 165119874688862080173619932344
896 172161834030074601453949201669
897 179500041038491344033961985679
898 187146789670867008373339972313
899 195114877167528676248584402853
900 203417624377271590893945824893
901 212068896891983871422101645101
902 221083127022860819529974089276
903 230475336651234196192386585995
904 240261160988394020311812408804
905 250456873280038420725095304824
906 261079410492442096220839002721
907 272146400018792451785887887743
908 283676187445708147609749272344
909 295687865421421675345790203583
910 308201303668792271920974790302
911 321237180187899151425277831322
912 334817013694777771337200848567
913 348963197344571382129222681318
914 363699033789320574259563692437
915 379048771622458692743984585903
916 395037643264179600161252562335
917 411691904343835551615704829916
918 429038874637780899171201399790
919 447106980623226053228910353206
920 465925799711095462377464020535
921 485526106223201668624308235341
922 505939919181661147074682728104
923 527200551980978599319659176166
924 549342664016038246178356398930
925 572402314341938359758494177672
926 596417017444630321233957012909
927 621425801204233052134370435321
928 647469267136147945832599867365
929 674589652998237130057235503570
930 702830897855828664116273630015
931 732238709699695624682203401834
932 762860635715921849919366856285
933 794746135310214929949982675068
934 827946655993277822322321551948
935 862515712237782995927737316407
936 898508967421850188367228162746
937 935984318978167853033452796659
938 975001986872584954522559161999
939 1015624605540568622650767325333
940 1057917319414963879415967633417
941 1101947882183415513948851713238
942 1147786759919233564029811891150
943 1195507238234789765447603446643
944 1245185533612362922923349210379
945 1296900909073068157306266475476
946 1350735794350775430955316345907
947 1406775910744082081170849003697
948 1465110400826147310969937244193
949 1525831963198831802423458720311
950 1589036992484836964882497107590
951 1654825724758685499222060014633
952 1723302388625182405936519278470
953 1794575362161693439315031460171
954 1868757335948962336007391121403
955 1945965482423478364097620992827
956 2026321631793420737042683532794
957 2109952454769133732577703999889
958 2196989652368779052862413185656
959 2287570153069424393860019671066
960 2381836317584248080713556798964
961 2479936151556888818353455070972
962 2582023526475172904299392511830
963 2688258409117592656193660421919
964 2798807099857953722374681271564
965 2913842480165602121936314610033
966 3033544269651588886933061723732
967 3158099293024039096366425693663
968 3287701757329909315322350620344
969 3422553539874210802863623914180
970 3562864487222735289056613447216
971 3708852725709271671889839606083
972 3860744983884380936385516278720
973 4018776927358885557180492440296
974 4183193506512511083389507513974
975 4354249317555429017798478159705
976 4532208977449023077485171177424
977 4717347513210826097218441856630
978 4909950766148534921609120019961
979 5110315811588047589424226069753
980 5318751394681916871865180244204
981 5535578382906168191681500549071
982 5761130235876479443818983653553
983 5995753493137904159293584120274
984 6239808280607086783863024658998
985 6493668836370853950991331912748
986 6757724056571677514036580674839
987 7032378062137321510002637372717
988 7318050787140577627901539188373
989 7615178589603831097162202989188
990 7924214885593917693048405926877
991 8245630807483740678992576251983
992 8579915887290118152306363157130
993 8927578766030670955011453016938
994 9289147930078013689520922038972
995 9665172475525355172841495879277
996 10056222901615697838819590149385
997 10462891934325358595814134389023
998 10885795381233440763050300545657
999 11325573018850307499318381020328
1000 11782889513622045349286050694219