0 0
1 0
2 1
3 1
4 3
5 4
6 7
7 10
8 16
9 22
10 32
11 44
12 62
13 83
14 113
15 149
16 199
17 259
18 339
19 436
20 563
21 716
22 913
23 1151
24 1453
25 1816
26 2271
27 2818
28 3496
29 4309
30 5308
31 6502
32 7959
33 9695
34 11798
35 14298
36 17309
37 20877
38 25151
39 30203
40 36225
41 43323
42 51748
43 61651
44 73359
45 87086
46 103254
47 122164
48 144363
49 170261
50 200568
51 235846
52 277007
53 324811
54 380437
55 444898
56 519715
57 606237
58 706412
59 822028
60 955587
61 1109429
62 1286762
63 1490651
64 1725186
65 1994358
66 2303388
67 2657439
68 3063159
69 3527215
70 4058041
71 4664213
72 5356431
73 6145663
74 7045454
75 8069818
76 9235841
77 10561364
78 12067930
79 13778162
80 15719164
81 17919571
82 20413391
83 23236771
84 26432338
85 30045565
86 34129778
87 38742095
88 43949063
89 49822243
90 56444587
91 63905511
92 72308222
93 81764257
94 92401752
95 104359545
96 117796516
97 132885074
98 149821880
99 168820701
100 190124499
101 213997796
102 240740363
103 270678872
104 304182581
105 341654291
106 383548076
107 430359749
108 482646938
109 541018834
110 606159202
111 678815459
112 759824718
113 850102510
114 950672361
115 1062653923
116 1187296860
117 1325968555
118 1480192565
119 1651636375
120 1842155128
121 2053779251
122 2288764628
123 2549580415
124 2838966100
125 3159920266
126 3515765665
127 3910138885
128 4347065056
129 4830949054
130 5366660730
131 5959528816
132 6615438339
133 7340827504
134 8142799721
135 9029124596
136 10008366036
137 11089889240
138 12284007505
139 13601996039
140 15056260985
141 16660362052
142 18429206352
143 20379082823
144 22527884843
145 24895158310
146 27502358355
147 30372914476
148 33532525545
149 37009246782
150 40833829297
151 45039832462
152 49664015909
153 54746483006
154 60331132298
155 66465839676
156 73202978799
157 80599648455
158 88718274056
159 97626889547
160 107399831146
161 118118085887
162 129870092527
163 142752167898
164 156869433239
165 172336333631
166 189277707735
167 207829419398
168 228139593743
169 250369379757
170 274694380746
171 301305572372
172 330410955831
173 362236661449
174 397028860200
175 435055083716
176 476606436741
177 521999172579
178 571577251233
179 625714217418
180 684816159156
181 749323938213
182 819716614435
183 896514090103
184 980281069686
185 1071630191695
186 1171226608277
187 1279791683953
188 1398108294473
189 1527025188809
190 1667463115631
191 1820419962604
192 1986977839755
193 2168309121213
194 2365684637215
195 2580480768069
196 2814188911723
197 3068423806108
198 3344934470096
199 3645613949437
200 3972511961642
201 4327846296977
202 4714017423747
203 5133621814789
204 5589468814199
205 6084596191676
206 6622289620616
207 7206100815704
208 7839870013691
209 8527747107675
210 9274217587826
211 10084127136915
212 10962711559923
213 11915625383688
214 12948976370407
215 14069358750231
216 15283893009761
217 16600264467204
218 18026769133645
219 19572358455377
220 21246692147761
221 23060190056997
222 25024093008228
223 27150522863931
224 29452552584694
225 31944275731037
226 34640887092559
227 37558763068584
228 40715554428834
229 44130279199647
230 47823429351466
231 51817078066500
232 56135002386077
233 60802807014393
234 65848065263971
235 71300461839593
236 77191954760824
237 83556939936413
238 90432437101493
239 97858279402879
240 105877326834741
241 114535684490062
242 123882947480011
243 133972452043256
244 144861556468571
245 156611929856624
246 169289874218950
247 182966656334407
248 197718876931150
249 213628851864913
250 230785035084553
251 249282456241957
252 269223205094371
253 290716933615222
254 313881410559401
255 338843097289342
256 365737782399234
257 394711241760293
258 425919964488428
259 459531909125093
260 495727333795141
261 534699662106753
262 576656432064608
263 621820287149871
264 670430060569196
265 722741909046226
266 779030551258547
267 839590564291678
268 904737797625168
269 974810854926641
270 1050172707870047
271 1131212388967066
272 1218346832790451
273 1312022809043729
274 1412719022414712
275 1520948319031271
276 1637260080390571
277 1762242740736309
278 1896526515264942
279 2040786271017635
280 2195744634855892
281 2362175266159471
282 2540906396148666
283 2732824557028441
284 2938878611084883
285 3160083998199475
286 3397527320789689
287 3652371179818066
288 3925859390391398
289 4219322485545007
290 4534183647160332
291 4871964967262964
292 5234294189913928
293 5622911831531469
294 6039678841949765
295 6486584698431148
296 6965756108190963
297 7479466205744646
298 8030144434971584
299 8620386996288727
300 9252968064251538
301 9930851649892894
302 10657204330018023
303 11435408711438256
304 12269077870669535
305 13162070630839086
306 14118507936062469
307 15142790178714304
308 16239615761486021
309 17414000743183053
310 18671299873621060
311 20017228860344733
312 21457888197880501
313 22999788396092681
314 24649876966147620
315 26415566994514040
316 28304767693701795
317 30325916754517612
318 32488014921230750
319 34800662609100606
320 37274099021515503
321 39919243581158327
322 42747740171466504
323 45772003998630306
324 49005271612725267
325 52461653894771469
326 56156192594765599
327 60104920224748912
328 64324923942583100
329 68834413229199118
330 73652792050021580
331 78800735303351575
332 84300270306839327
333 90174863126235633
334 96449510563514842
335 103150837612222109
336 110307201268977984
337 117948800514870202
338 126107793434603779
339 134818421295391320
340 144117140639750722
341 154042763225911090
342 164636604964154154
343 175942643698028483
344 188007687082300276
345 200881550425647698
346 214617245863308667
347 229271182751956232
348 244903380775902436
349 261577695686587671
350 279362059300777504
351 298328733715038886
352 318554581511357564
353 340121351954758612
354 363115985121394137
355 387630934009372645
356 413764506750933214
357 441621229038603365
358 471312229081660028
359 502955645277067804
360 536677059127986643
361 572609953677534787
362 610896200229733691
363 651686573722056749
364 695141299783944762
365 741430633958547738
366 790735476410159831
367 843248022724841643
368 899172454444309527
369 958725670090080637
370 1022138060667300882
371 1089654330577722534
372 1161534368315221732
373 1238054168070804037
374 1319506807043996508
375 1406203479812753260
376 1498474595025007422
377 1596670936021756585
378 1701164891167757717
379 1812351755793065974
380 1930651112087524844
381 2056508289184252941
382 2190395910397838695
383 2332815530231965244
384 2484299368808845316
385 2645412146764149607
386 2816753029017826312
387 2998957680949215130
388 3192700446222500762
389 3398696650339856421
390 3617705040089132487
391 3850530363582949742
392 4098026102072851844
393 4361097358933154500
394 4640703918119649365
395 4937863478285048231
396 5253655076092842719
397 5589222705797199752
398 5945779149996289317
399 6324610029621604981
400 6727078089577641220
401 7154627729213534321
402 7608789795703297271
403 8091186650772057773
404 8603537530681173622
405 9147664211317064808
406 9725497000323391845
407 10339081069700292959
408 10990583153046697866
409 11682298622637402350
410 12416658972981583278
411 13196239728031970186
412 14023768801418917136
413 14902135329092132392
414 15834399006754706810
415 16823799953946165056
416 17873769140485006856
417 18987939399889944479
418 20170157069162391603
419 21424494282635683680
420 22755261963327048107
421 24167023542941501433
422 25664609458441705494
423 27253132460172421355
424 28938003784398052196
425 30724950229524291002
426 32620032194320686935
427 34629662722186468798
428 36760627615805913163
429 39020106671548080665
430 41415696104614573372
431 43955432220206744074
432 46647816409065205657
433 49501841529236610043
434 52527019760537620125
435 55733412000892329196
436 59131658899974674133
437 62733013607475276335
438 66549376341316451821
439 70593330862185195990
440 74878182970631700441
441 79418001123156610040
442 84227659295593332324
443 89322882201377389587
444 94720293006318382502
445 100437463659866265876
446 106492967999181524017
447 112906437759760862556
448 119698621665145743100
449 126891447744735512016
450 134508089070128862312
451 142573033075951691159
452 151112154675348603534
453 160152793354872672513
454 169723834480747786629
455 179855795022055055054
456 190580913946865708602
457 201933247519939179981
458 213948769784544968350
459 226665478482578252189
460 240123506724801871441
461 254365240693686724499
462 269435443722972347879
463 285381387067754670737
464 302252987744841790653
465 320102953791865852350
466 338986937364174838025
467 358963696056374747589
468 380095262910862902733
469 402447125542684592126
470 426088414890822502533
471 451092104072211194904
472 477535217901252317007
473 505499053603053727656
474 535069413341225149429
475 566336849145860776443
476 599396920926543287496
477 634350468219442658980
478 671303896423884912864
479 710369478247570864267
480 751665671193555768535
481 795317451885614928712
482 841456668150771568815
483 890222409741140744348
484 941761398708250835525
485 996228400406442565516
486 1053786656242484100749
487 1114608339252264371446
488 1178875033736244751382
489 1246778240149601154667
490 1318519906604892470919
491 1394312988310170532767
492 1474382036439294516194
493 1558963817897456196003
494 1648307967631664191720
495 1742677675103710030878
496 1842350406743799880678
497 1947618666172780632831
498 2058790794196563471237
499 2176191810548554939833
500 2300164299587802750003
501 2431069342135769790532
502 2569287495884076441643
503 2715219826784387237070
504 2869288994099972329687
505 3031940391781643513798
506 3203643349119589536412
507 3384892393610907859829
508 3576208579293594618343
509 3778140883792020557526
510 3991267677653815473930
511 4216198269559334050322
512 4453574531345673426028
513 4704072606796532548230
514 4968404708538039635093
515 5247321007399304782584
516 5541611619015626707393
517 5852108692481602217898
518 6179688606313421378518
519 6525274277021149620669
520 6889837586079433831336
521 7274401931140499945026
522 7680044907859497377417
523 8107901128773485661872
524 8559165186243340723864
525 9035094766556987308315
526 9537013922905657732858
527 10066316515054239829850
528 10624469824189177840059
529 11213018351559577620110
530 11833587810242841889296
531 12487889319524013919416
532 13177723812151479001957
533 13904986664918376045092
534 14671672563855227124851
535 15479880615538360948469
536 16331819716922906544203
537 17229814196364418752805
538 18176309739471265201370
539 19173879613725708082062
540 20225231206869850564973
541 21333212894393679322074
542 22500821252607743210695
543 23731208634174521014121
544 25027691124212415102644
545 26393756895534050132594
546 27833074982923142689755
547 29349504496864538533561
548 30947104298596202644220
549 32630143158931832262546
550 34403110424878229166776
551 36270727218728733752791
552 38237958196021257188152
553 40310023889492390111666
554 42492413668009545839306
555 44790899340301115826635
556 47211549435310824882706
557 49760744191945863393204
558 52445191293163858934991
559 55271942380403812521769
560 58248410386725697506333
561 61382387728212527789196
562 64682065395748477320166
563 68156052990618448025100
564 71813399750151956067160
565 75663616611123716717237
566 79716699361637599258623
567 83983152933884229366713
568 88474016893434432638503
569 93200892182586488912100
570 98175969178837307735482
571 103412057131615395793994
572 108922615044270540203971
573 114721784070616548598587
574 120824421499512220158789
575 127246136403524640712637
576 134003327032268702664633
577 141113220033859292696478
578 148593911592855249535297
579 156464410576228917468092
580 164744683784265327373578
581 173455703406793319272196
582 182619496790986383526607
583 192259198630847186619741
584 202399105694831626214671
585 213064734212359891822401
586 224282880046855099642111
587 236081681787698335587701
588 248490686900981948310210
589 261540921084192893385326
590 275264960978103986964579
591 289697010394951802650344
592 304872980230836883414247
593 320830572236687687275639
594 337609366831760385299691
595 355250915150716235261217
596 373798835525791292784242
597 393298914613371092596788
598 413799213385672945853795
599 435350178216835168095088
600 458004757305100700892892
601 481818522682255120159329
602 506849798074953787198014
603 533159792893005401538123
604 560812742634336882536812
605 589876056007849009796280
606 620420469091317535782588
607 652520206854131480881740
608 686253152392007333685795
609 721701024234717010076568
610 758949562106740340332816
611 798088721536033979236623
612 839212877726642484820347
613 882421039127671252142509
614 927817071153482881877361
615 975509930528427988215404
616 1025613910753731442591018
617 1078248899214415813038821
618 1133540646470595892446246
619 1191621048299720330276609
620 1252628441085120202617549
621 1316707911170633180327057
622 1384011618832393659122861
623 1454699137545657082742316
624 1528937809258610476559951
625 1606903116414488742260715
626 1688779071500406222028331
627 1774758624933510657357209
628 1865044092135428285060862
629 1959847600681258809829615
630 2059391558453300903249585
631 2163909143768357125352632
632 2273644818495263511273616
633 2388854865221646959286292
634 2509807949580925957619805
635 2636785708896957268962821
636 2770083368360330999247601
637 2910010386001102639883156
638 3056891127784341933270748
639 3211065574210466429493970
640 3372890059869349614186529
641 3542738047458022298725154
642 3721000937844716186111149
643 3908088917828546104934022
644 4104431847323485173597590
645 4310480187768073776554004
646 4526705973648653080339178
647 4753603829103506175111533
648 4991692031669245311227208
649 5241513625317798644022964
650 5503637585034577890115981
651 5778660035283517019972255
652 6067205524815897663684443
653 6369928360383810141138681
654 6687514002040109787161042
655 7020680522820281077999901
656 7370180135733274251977531
657 7736800791112416385265980
658 8121367847520722805344177
659 8524745819540397550283400
660 8947840205932117791276497
661 9391599401797609137443501
662 9857016698548505450235314
663 10345132375645960991913606
664 10857035888259842898955577
665 11393868155172579051233355
666 11956823951453265615763501
667 12547154410619974829712591
668 13166169641226309395870077
669 13815241463018106156477802
670 14495806268043402747172506
671 15209368012327712945650448
672 15957501343984632454443196
673 16741854873881495437741687
674 17564154595260345839020980
675 18426207458986789936265856
676 19329905111404365248612264
677 20277227802068964081667402
678 21270248468969568294960859
679 22311137009165225383880420
680 23402164743128870905187134
681 24545709081441402832941061
682 25744258402871549204114794
683 27000417153261558498938303
684 28316911175065056572863014
685 29696593277802370542041929
686 31142449060162063126425963
687 32657602994933865885574418
688 34245324788461973107216086
689 35909036026804871134943639
690 37652317121335455167489933
691 39478914567056727678734371
692 41392748527503523416751592
693 43397920760690442792661461
694 45498722901212989631927704
695 47699645114251037706095085
696 50005385137926664424105299
697 52420857731167465365914288
698 54951204544990290174078464
699 57601804435881305915002424
700 60378284240778254231246615
701 63286530033988989648263880
702 66332698887282141595414774
703 69523231155287040667743680
704 72864863309319740390064865
705 76364641343732656243523856
706 80029934779949628637609402
707 83868451294415151644659398
708 87888251997842607904100169
709 92097767394306962453021261
710 96505814049983108562694844
711 101121612002593409248165090
712 105954802943991846538956893
713 111015469209685022379880242
714 116314153610571450387375219
715 121861880143673371373532643
716 127670175620243819414787753
717 133751092251254700107608407
718 140117231232018242378153020
719 146781767369458606594953559
720 153758474797446849063886721
721 161061753827530333068421726
722 168706658984446603708357581
723 176708928277896198605447775
724 185085013764284055825275949
725 193852113454404394947531415
726 203028204625470298219118195
727 212632078598350576763738674
728 222683377043510162027618901
729 233202629881824433895819003
730 244211294849296342830486165
731 255731798797610231067757097
732 267787580805558434841429547
733 280403137179532243814252104
734 293604068424635216750766886
735 307417128271403993321862827
736 321870274846774628007404449
737 336992724081654225045529660
738 352815005451421061030714158
739 369369020149717621088785949
740 386688101800200955388970761
741 404807079815302426890124863
742 423762345515713681489479585
743 443591921129078933904953678
744 464335531791433738259380880
745 486034680680100861534717170
746 508732727412242326291720895
747 532474969848878526326476409
748 557308729450137921978763790
749 583283440333591074891745245
750 610450742193978267802891425
751 638864577249248706685281816
752 668581291384829585857207342
753 699659739675213932437948227
754 732161396469546585831905180
755 766150470235667145707554975
756 801694023365298397529667431
757 838862097151507863089591963
758 877727842158492140764085154
759 918367654212887490041354937
760 960861316255481927943345208
761 1005292146302132048965654312
762 1051747151773171541995414369
763 1100317190461364853194425699
764 1151097138419822387503223680
765 1204186065062968292733767232
766 1259687415785966716245521498
767 1317709202420670589395697568
768 1378364201859502391813767375
769 1441770163192399514941080187
770 1508050023716417847418091000
771 1577332134192463506440823330
772 1649750493739291223363407326
773 1725444994771032639390743634
774 1804561678401493380141769162
775 1887253000755934037095554412
776 1973678110649440347910712600
777 2064003139109927078039952676
778 2158401501243741061679785197
779 2257054210962351508355012077
780 2360150209110193083256339426
781 2467886705555963610227853382
782 2580469535833047917540026903
783 2698113532938830181431377907
784 2821042914927965863485629454
785 2949491688960781859775496532
786 3083704072495379941447230615
787 3223934932340287264773693742
788 3370450242314173358716992991
789 3523527560289770636205192912
790 3683456525431265532618994488
791 3850539376467586048943826415
792 4025091491878796127299942519
793 4207441952908714560441729302
794 4397934130354531638471433322
795 4596926296123076867623004916
796 4804792260584151072432239355
797 5021922036793431460085442426
798 5248722532701575038269081710
799 5485618272511717903007577050
800 5733052148395314146183970923
801 5991486203825589816534324971
802 6261402449839557423857599713
803 6543303715592933060994160928
804 6837714534628210035962250353
805 7145182068333934157458767954
806 7466277068133722732195386296
807 7801594878006111361198763555
808 8151756479001765362852313183
809 8517409577492269993966088311
810 8899229738955522478980071352
811 9297921569175976709751429998
812 9714219944814588558767540975
813 10148891295382536367112893704
814 10602734938735643001951916883
815 11076584472292135182956993832
816 11571309222265985935430963171
817 12087815753300800393147137389
818 12627049440986117196773432313
819 13189996109838280997470967022
820 13777683739432842092761432040
821 14391184241483899933810426709
822 15031615310779129341376160244
823 15700142352996523179473455041
824 16397980492551412088479967032
825 17126396663749159704023898279
826 17886711788651400559058672219
827 18680303045200833336038826072
828 19508606229292788182931104106
829 20373118214630065031123412941
830 21275399514352341261661401283
831 22217076948591748228630930533
832 23199846422273538604630369938
833 24225475817654050934560816700
834 25295808006269019821958976345
835 26412763985152583751712844307
836 27578346142382781213185660506
837 28794641657211765863391700341
838 30063826040250168378093151194
839 31388166819393814303288731638
840 32770027377409215133344585230
841 34211870947330672731230625093
842 35716264772068407070439053967
843 37285884434882582877862494920
844 38923518367644499284274138614
845 40632072544082226110218071908
846 42414575365495748247609617571
847 44274182746724882437267805362
848 46214183410464091243563250430
849 48238004398340461877094433736
850 50349216807506886217639771323
851 52551541761850455044621846827
852 54848856627278724251750693624
853 57245201480922362723644349269
854 59744785844484333543486341033
855 62351995692371687777629287646
856 65071400745668975501048507027
857 67907762063450653613103594467
858 70866039943386542752762484930
859 73951402144067763776700181356
860 77169232441973659619117491371
861 80525139536511344181057796449
862 84024966317091859083902219377
863 87674799506758780675798708067
864 91480979697459805666802287567
865 95450111792647629071194118538
866 99589075873516782576887691645
867 103905038505826256072385351338
868 108405464504927326509945433275
869 113098129177310254196708489337
870 117991131057706210097508153783
871 123092905161530113682070258260
872 128412236773230018981000401385
873 133958275791917389804815974452
874 139740551656494290644792256888
875 145768988873366249769491005437
876 152053923170737781359369212234
877 158606118304429306875801922396
878 165436783541134179004574166193
879 172557591846050669294051685122
880 179980698802881063460570682614
881 187718762295286365193172997516
882 195784962980025727817074996443
883 204193025583192528685832273347
884 212957241052189432921525290559
885 222092489597360745451819855994
886 231614264658527569305584882413
887 241538697833047630251880204601
888 251882584803453142201693757024
889 262663412304204606377408635159
890 273899386168642329324894711353
891 285609460498818522043866396499
892 297813368002557812404480204219
893 310531651543820661390353197739
894 323785696954239585729088020627
895 337597767155560040210091245232
896 351991037644653745689719323018
897 366989633394779943546385359905
898 382618667228857357237135078855
899 398904279722674328204824772238
900 415873680698214932634147454260
901 433555192369612667745956636077
902 451978294206669234765100640015
903 471173669583391847416470099789
904 491173254281617546512532104304
905 512010286922505035559614698068
906 533719361401493257072052317563
907 556336481405249172667669134632
908 579899117092165210150116127988
909 604446264021117512380148045981
910 630018504416470245525480315969
911 656658070860706771547953209813
912 684408912509596836012858268485
913 713316763928468112696888752023
914 743429216651952485495983916203
915 774795793573520467572177302381
916 807468026275213829485581608119
917 841499535412235066697912881324
918 876946114271466161589345100227
919 913865815627566540862009968638
920 952319042025055324894484437248
921 992368639619714405900217798880
922 1034079995717771500417461148592
923 1077521140156634754362221610414
924 1122762850676468502149181536815
925 1169878762437622235124988501959
926 1218945481844868379080328552203
927 1270042704845568165423468861328
928 1323253339875286314131839712528
929 1378663635631013715670393037970
930 1436363313859051417991607365089
931 1496445707351758547877349609723
932 1559007903354791004976275113516
933 1624150892594156716747003477521
934 1691979724140407747809741021136
935 1762603666335579809040198118287
936 1836136374017097727458037101048
937 1912696062281791783986367147671
938 1992405687042437796781364568124
939 2075393132638844407174022766603
940 2161791406775488863701279130095
941 2251738843068049145123037643648
942 2345379311491921606423158302214
943 2442862437036951434296540420065
944 2544343826884165681315086670547
945 2649985306432288040665668390159
946 2759955164514260072605248766049
947 2874428408156898456384431306392
948 2993587027250212991543803825900
949 3117620269506799357831931499900
950 3246724926106136873969534855073
951 3381105628433569279715458800663
952 3520975156339260665645622174926
953 3666554758358504533222215930382
954 3818074484351458421962316716459
955 3975773531037685949256869001369
956 4139900600918851516395282227931
957 4310714275101537703701264944409
958 4488483400551482900282141591100
959 4673487492330575450296241967556
960 4866017151388734436374554145039
961 5066374498504365823495558168939
962 5274873624989452597752252913401
963 5491841060798529727481444930818
964 5717616260704858619747746174710
965 5952552109232063648078454367778
966 6197015445055377665555851611930
967 6451387605613478156520749790507
968 6716064992699736398827179613174
969 6991459659830564372645218499486
970 7277999922218487146806756155709
971 7576130990208609616163610119321
972 7886315627069348365903197903491
973 8209034832061681630886824398456
974 8544788549745799274016560175466
975 8894096406519932145206821789906
976 9257498475423376688016384278826
977 9635556070274330329098059535181
978 10028852570253190981871780741348
979 10437994276083476595311342539565
980 10863611299005567711284928520526
981 11306358483783096934122720049055
982 11766916367028088662375985285632
983 12245992172178922895307753682142
984 12744320842514948297020009481386
985 13262666113643137779406477228152
986 13801821626945660182369337849852
987 14362612085532673549679179340854
988 14945894454302130561849735873201
989 15552559205767968115375279005980
990 16183531613379838774881391204625
991 16839773094121579268408854202357
992 17522282602242015115471626119618
993 18232098076040522786314945141865
994 18970297939701133532893247031556
995 19738002662242923004352887106548
996 20536376375731117760685070174341
997 21366628554972825902441415994555
998 22230015761003702307158492006291
999 23127843450757257181203613750424
1000 24061467855397056677947994566485