3 1
4 0
5 1
6 2
7 3
8 3
9 6
10 8
11 13
12 15
13 24
14 30
15 44
16 54
17 77
18 98
19 134
20 165
21 222
22 279
23 367
24 454
25 588
26 731
27 936
28 1148
29 1454
30 1788
31 2241
32 2732
33 3400
34 4140
35 5106
36 6183
37 7579
38 9157
39 11156
40 13406
41 16249
42 19482
43 23489
44 28042
45 33666
46 40087
47 47914
48 56851
49 67691
50 80107
51 95039
52 112112
53 132565
54 155999
55 183866
56 215754
57 253555
58 296841
59 347857
60 406209
61 474775
62 553211
63 644957
64 749774
65 872051
66 1011727
67 1174038
68 1359212
69 1573897
70 1818668
71 2101560
72 2423715
73 2795230
74 3217990
75 3704226
76 4256876
77 4891237
78 5611661
79 6436679
80 7372519
81 8442340
82 9654754
83 11037930
84 12603696
85 14387058
86 16403970
87 18697044
88 21287545
89 24228318
90 27547431
91 31309209
92 35550452
93 40350716
94 45757692
95 51868345
96 58744369
97 66505232
98 75230044
99 85064469
100 96109525
101 108544367
102 122497334
103 138186594
104 155774709
105 175529352
106 197655336
107 222478495
108 250256285
109 281387420
110 316194173
111 355161544
112 398691764
113 447377198
114 501718449
115 562434891
116 630148178
117 705734962
118 789964704
119 883900829
120 988494121
121 1105037531
122 1234702648
123 1379055698
124 1539537578
125 1718048770
126 1916357552
127 2136762176
128 2381428940
129 2653140795
130 2954545796
131 3289004290
132 3659748481
133 4070838700
134 4526212661
135 5030764867
136 5589285080
137 6207675891
138 6891753800
139 7648621525
140 8485332244
141 9410435094
142 10432468963
143 11561703801
144 12808464044
145 14185086511
146 15704036101
147 17380107208
148 19228329606
149 21266442078
150 23512542496
151 25987866348
152 28714179780
153 31716897616
154 35022163516
155 38660350572
156 42662825562
157 47065872507
158 51907078800
159 57229733754
160 63078829620
161 69505989534
162 76565008396
163 84317372129
164 92827333317
165 102168088016
166 112416295687
167 123658993560
168 135987553054
169 149505411726
170 164321363671
171 180558207065
172 198345355836
173 217828506349
174 239161450122
175 262516876844
176 288077379007
177 316047516899
178 346643872054
179 380108526424
180 416698150763
181 456699051201
182 500415132695
183 548184699231
184 600367273607
185 657362346774
186 719594870656
187 787536180791
188 861688149720
189 942606524227
190 1030883524844
191 1127173884313
192 1232175878259
193 1346660360823
194 1471449992698
195 1607451624737
196 1755633708094
197 1917062402073
198 2092876901947
199 2284329700425
200 2492759834807
201 2719637767310
202 2966536251338
203 3235180375352
204 3527416061944
205 3845265845604
206 4190894689988
207 4566672172021
208 4975135645187
209 5419059555602
210 5901415609866
211 6425450053383
212 6994640915433
213 7612784149872
214 8283947596201
215 9012567028401
216 9803396954052
217 10661617684467
218 11592782624453
219 12602937662936
220 13698565137166
221 14886716959061
222 16174954915787
223 17571499142136
224 19085165068088
225 20725528999611
226 22502861410667
227 24428311662924
228 26513838101057
229 28772414107330
230 31217954801258
231 33865546964886
232 36731373000785
233 39832967507225
234 43189138432664
235 46820253461877
236 50748159335623
237 54996501525610
238 59590641863530
239 64558015500115
240 69928048196980
241 75732554926775
242 82005657327408
243 88784228944730
244 96107814724136
245 104019128407687
246 112563975030791
247 121791806733552
248 131755650890877
249 142512731272537
250 154124403414618
251 166656849043552
252 180181022271386
253 194773425998934
254 210516071506508
255 227497346778345
256 245811994343186
257 265562082544620
258 286857005460631
259 309814569620992
260 334561022603111
261 361232269093358
262 389973933673151
263 420942722035365
264 454306526795848
265 490245951369964
266 528954466685406
267 570640117633309
268 615525742441656
269 663850883865162
270 715872082159154
271 771865016100285
272 832124885238217
273 896968808722274
274 966736311821851
275 1041792014283510
276 1122526241833258
277 1209358039367561
278 1302735927864734
279 1403141282439714
280 1511089261897584
281 1627132596342586
282 1751862716826946
283 1885914003008200
284 2029965148725963
285 2184743926135723
286 2351028823838793
287 2529654391330576
288 2721513196512963
289 2927561821711470
290 3148823189244899
291 3386393289606171
292 3641443936066243
293 3915230315139602
294 4209094234412907
295 4524472596985793
296 4862901221892901
297 5226024356313073
298 5615599152794176
299 6033506347716773
300 6481755498147765
301 6962496970214084
302 7478028045748415
303 8030806382695345
304 8623457124420593
305 9258788013639235
306 9939797647751875
307 10669692450769152
308 11451896246173699
309 12290069315853401
310 13188119476351333
311 14150223482867937
312 15180839829517025
313 16284732787206082
314 17466987168368827
315 18733035324026546
316 20088674156173473
317 21540095438333621
318 23093905385526470
319 24757158708209248
320 26537381102789750
321 28442607498054791
322 30481407864552073
323 32662930169992156
324 34996929971583469
325 37493818658557484
326 40164697338472340
327 43021411016991396
328 46076587370364018
329 49343697590492939
330 52837100697261725
331 56572111866781591
332 60565053038264212
333 64833329641315536
334 69395488331657568
335 74271303146132181
336 79481841327081273
337 85049560056388536
338 90998381431597726
339 97353801071568464
340 104142973462903203
341 111394833884038951
342 119140195473520455
343 127411886095580899
344 136244858675401515
345 145676344822596155
346 155745980148571375
347 166495976685023601
348 177971265139128956
349 190219688385838935
350 203292162834109244
351 217242895547509884
352 232129567193200898
353 248013575648140608
354 264960243279467762
355 283039090237159126
356 302324069185864258
357 322893871863404000
358 344832194734933766
359 368228082825733582
360 393176230230050639
361 419777365698766476
362 448138592379794822
363 478373820175988513
364 510604149666629278
365 544958356840522986
366 581573326709387298
367 620594596686390018
368 662176846113968704
369 706484505293131567
370 753692307854402526
371 803985973271829364
372 857562829889336718
373 914632579667984172
374 975418000568377399
375 1040155803310222791
376 1109097422906952767
377 1182509978355328078
378 1260677164233048045
379 1343900325515779202
380 1432499461507858239
381 1526814429399855316
382 1627206074197427047
383 1734057576222021526
384 1847775722388062477
385 1968792414606860985
386 2097566099507163139
387 2234583456674388414
388 2380361005996069057
389 2535446996850609399
390 2700423214437198231
391 2875907093471761606
392 3062553747445265423
393 3261058333090281071
394 3472158329225164431
395 3696636181282242365
396 3935321859593315773
397 4189095816621322989
398 4458891857920981197
399 4745700448463314293
400 5050571933458324222
401 5374620234310737927
402 5719026460690947009
403 6085043041293573224
404 6473997773429213136
405 6887298438888973897
406 7326437342541111892
407 7792996469331540768
408 8288652569403716755
409 8815182918605137513
410 9374471014111810913
411 9968513007882450913
412 10599424084213829495
413 11269445643414273184
414 11980952440720422586
415 12736460606185075797
416 13538635633568571172
417 14390301332096639885
418 15294448763839098008
419 16254246233750058473
420 17273049285363038323
421 18354411847433322814
422 19502097410012944879
423 20720091459266737775
424 22012613969924567529
425 23384133274511830730
426 24839380023278626542
427 26383362650396229245
428 28021382969611580824
429 29759053418016946196
430 31602314474299091897
431 33557453880754798745
432 35631126092092205235
433 37830373698568270267
434 40162649136242168109
435 42635838558774295732
436 45258286065942529259
437 48038820298930713401
438 50986781472155858919
439 54112050997163695271
440 57425081634634107590
441 60936930485511259070
442 64659292614773229763
443 68604537785601325717
444 72785747945544533725
445 77216758120647808942
446 81912198197297436396
447 86887538438822659706
448 92159136044180648414
449 97744285799961254483
450 103661271949427968560
451 109929424548728792934
452 116569177238471339413
453 123602129934712963493
454 131051113159455962543
455 138940257765416736187
456 147295066553655291447
457 156142491806745692821
458 165511015000435330547
459 175430733003576412058
460 185933446778593373954
461 197052757199057247258
462 208824163730074623557
463 221285170916782475519
464 234475398143231618567
465 248436697958192661397
466 263213278128956779801
467 278851833095975613488
468 295401679669303050780
469 312914903041775401740
470 331446507619882980934
471 351054579178002912711
472 371800452475804453577
473 393748891304747791661
474 416968274720098823585
475 441530796917371766058
476 467512674102645963899
477 494994366342440224680
478 524060807310798973589
479 554801650483478420378
480 587311524238793430170
481 621690305017897553619
482 658043400518332145161
483 696482052719291451259
484 737123652197454341070
485 780092074221801651391
486 825518027540558969622
487 873539427087594739395
488 924301780943216693320
489 977958603566330062308
490 1034671845020620407415
491 1094612349057347658728
492 1157960329129120519899
493 1224905876100971517708
494 1295649486047087162051
495 1370402622867296541498
496 1449388303385844548477
497 1532841720700929322148
498 1621010892680031199339
499 1714157352477202116590
500 1812556867155939584368
501 1916500202477817470085
502 2026293919083196898370
503 2142261219392143391152
504 2264742829546263426141
505 2394097937075041507416
506 2530705167651378503384
507 2674963623071504364180
508 2827293962814978290561
509 2988139552871909389548
510 3157967663128918672550
511 3337270738663098643786
512 3526567725113401460506
513 3726405475255976936979
514 3937360215770572536339
515 4160039103228074968194
516 4395081847040913414607
517 4643162430442132285192
518 4904990905924014761398
519 5181315298382611394367
520 5472923591019814277282
521 5780645829581667799768
522 6105356318534478618508
523 6447975947255923533457
524 6809474618318816496044
525 7190873818617605424855
526 7593249303815105547778
527 8017733939723185802912
528 8465520669415478801115
529 8937865652749905570168
530 9436091545338048183449
531 9961590966922335957186
532 10515830124352458304236
533 11100352642635659927543
534 11716783567319941409915
535 12366833595450316062303
536 13052303496335193083621
537 13775088783393744372219
538 14537184596207883761202
539 15340690858369991496875
540 16187817668042516341615
541 17080890991446209539770
542 18022358613890101158871
543 19014796423518742421203
544 20060914979989115580251
545 21163566448563267324560
546 22325751849329753917591
547 23550628707734049601066
548 24841519053531581794935
549 26201917860443061923440
550 27635501870926120001249
551 29146138904884329032362
552 30737897593927038666124
553 32415057647010123794507
554 34182120586170569957264
555 36043821065703395174837
556 38005138710493859368822
557 40071310594911517151786
558 42247844294882030772090
559 44540531643188951855909
560 46955463117429306484171
561 49499042999944002111005
562 52178005235864015691468
563 54999430138540486515235
564 57970761865129957662087
565 61099826822270081075154
566 64394852921167182331092
567 67864489853481631798527
568 71517830303808928822794
569 75364432282425723908423
570 79414342490511229002811
571 83678120914702091711836
572 88166866559549573964573
573 92892244528889309256881
574 97866514361010190517237
575 103102559843832322946223
576 108613920211271488227245
577 114414822963315072001370
578 120520218207269301484712
579 126945814780230076332799
580 133708118046530133912364
581 140824469649034375040481
582 148313089104363661563391
583 156193117541142599397420
584 164484663467739355531821
585 173208850890314677836669
586 182387869664127572512157
587 192045028422263892390180
588 202204809961339726259765
589 212892929453432613490555
590 224136395360562574744226
591 235963573447950115306101
592 248404253769352092627619
593 261489721049693791757985
594 275252828335537453928295
595 289728074369787116037829
596 304951684558725089786220
597 320961696021304110427432
598 337798046586726496312709
599 355502668266302093146408
600 374119585064003188107123
601 393695015690498505251132
602 414277481044004007040182
603 435917917064478445841667
604 458669792824041469674798
605 482589234505054087077759
606 507735155129001802292900
607 534169390735968412607906
608 561956842878935537141742
609 591165628184727713212527
610 621867234847891389886802
611 654136686865357274395701
612 688052715881322342736873
613 723697941510519033035527
614 761159060013706556756345
615 800527042258523347424652
616 841897340845353126128172
617 885370107401310323870956
618 931050419929425253588452
619 979048521291521250827298
620 1029480068721109635481596
621 1082466395526002505514837
622 1138134784888266599882602
623 1196618757008741664934234
624 1258058369517349617376879
625 1322600532490728897131878
626 1390399338014615276459273
627 1461616405734177567260359
628 1536421244348826271643724
629 1614991630604295568910043
630 1697514005760863440818023
631 1784183891208690856670740
632 1875206323235119111106428
633 1970796308742327202186528
634 2071179301950212750927908
635 2176591704020341916832745
636 2287281385670364658583824
637 2403508234862972990460267
638 2525544729678351800711713
639 2653676538614132929150765
640 2788203148466930819367677
641 2929438522212004777842906
642 3077711787086448782635047
643 3233367955478654059946540
644 3396768678887633141981710
645 3568293037755874530245728
646 3748338367505115213812360
647 3937321123795590955598559
648 4135677787412370338939959
649 4343865812033433134761536
650 4562364615366635674352845
651 4791676617162986063392313
652 5032328324687200992384716
653 5284871469425851581535205
654 5549884195719269980050968
655 5827972305392227249122370
656 6119770559187296458971821
657 6425944039394148957375707
658 6747189574610276080011422
659 7084237231370138713519070
660 7437851873725056598579896
661 7808834795882126911186358
662 8198025429148095256415158
663 8606303128687606027564056
664 9034589041523841502418972
665 9483848061724332312743492
666 9955090874402364317287024
667 10449376094945048516160029
668 10967812505323238337794165
669 11511561394400354195729194
670 12081839004344618142710075
671 12679919090608631099644979
672 13307135597857079375641873
673 13964885459897520669487575
674 14654631526300929835368568
675 15377905624405825498808702
676 16136311759731032281203333
677 16931529464181459027831143
678 17765317295445954731610266
679 18639516497718208628694000
680 19556054827552818162200240
681 20516950555794606677462671
682 21524316649849184032202859
683 22580365148105553631632518
684 23687411731281510586603912
685 24847880503446247934150956
686 26064308988045012997842216
687 27339353352700677003893476
688 28675793868727349264210032
689 30076540620234382325152525
690 31544639469427684461025738
691 33083278294180159237373309
692 34695793505217227846171192
693 36385676860279998083021190
694 38156582583424626111541336
695 40012334808216588148550951
696 41956935353871384992315660
697 43994571854610501865830982
698 46129626252264979276655396
699 48366683674028999749645758
700 50710541706472641469940159
701 53166220089483286039907425
702 55738970842426441599587947
703 58434288848107199249533538
704 61257922908119116066663038
705 64215887297229877698850392
706 67314473831811470683911393
707 70560264482201805996398515
708 73960144545562740152212001
709 77521316411542263933174865
710 81251313939011705775373667
711 85158017478805060667511034
712 89249669562599334206920398
713 93534891295697031324116439
714 98022699475894531524342762
715 102722524479264050200513514
716 107644228937270500303541123
717 112798127249369025438419241
718 118195005957952142425001148
719 123846145033382754800662227
720 129763340098658446514908063
721 135958925645328436805650027
722 142445799273134389136396620
723 149237447009200679943680764
724 156347969742442606472531718
725 163792110833567496067195646
726 171585284939830133329713875
727 179743608119840594142584378
728 188283929261400671940132816
729 197223862902994372405017346
730 206581823496073739063258000
731 216377061184530638902049906
732 226629699153042023683105430
733 237360772626917927657159997
734 248592269580100707541839831
735 260347173240696088318433088
736 272649506456096620074748570
737 285524378014383904932166497
738 298998030989972935607786124
739 313097893218091032777879515
740 327852629972490929423850911
741 343292198959545911510754814
742 359447907710142769582186205
743 376352473491778794927432960
744 394040085829925192084834796
745 412546471771081675518446347
746 431908963984916392178379580
747 452166571848757362151660117
748 473360055620905798554884191
749 495532003857768875731533363
750 518726914191167342354644495
751 542991277633510154310190768
752 568373666537955087468776453
753 594924826394983795688814392
754 622697771604228009824966680
755 651747885417838968275083432
756 682133024206990593506947838
757 713913626263891228135658470
758 747152825304773199934085202
759 781916568903636942104269269
760 818273742037318824948659334
761 856296295990487830359103380
762 896059382817565557655258654
763 937641495630546536681671311
764 981124614927577031047485699
765 1026594361253310030336513629
766 1074140154425319076100604383
767 1123855379641434836635954098
768 1175837560723404780336274267
769 1230188540837538176777388308
770 1287014670970691291502525647
771 1346427006530164969701886391
772 1408541512370816151615897376
773 1473479276648148432271416156
774 1541366733827790353369406129
775 1612335897282788714610919793
776 1686524601838575295345478863
777 1764076756732365804306627937
778 1845142609378838930158199552
779 1929879020447072694513057699
780 2018449750675328572796155434
781 2111025759969999501410289353
782 2207785519253038939583865875
783 2308915335648900404624254030
784 2414609691516265286588742334
785 2525071597963948870938935422
786 2640512963400727388821773319
787 2761154977810779955883985822
788 2887228513352750041832307764
789 3018974542030686128627868907
790 3156644571087241313983956142
791 3300501096928564745828295208
792 3450818078288095208283754602
793 3607881429504841990739704580
794 3771989534685019583256725316
795 3943453783694155635601813151
796 4122599130815420775106089604
797 4309764677098649574381352486
798 4505304277308342017828786271
799 4709587172578750124482128367
800 4922998649763006360493167993
801 5145940728674824937714368989
802 5378832878295032385041795600
803 5622112763239223868739601382
804 5876237021651280570572290581
805 6141682075924738376256775783
806 6418944977516992377964210696
807 6708544287372588138326860796
808 7011020993329242302257614040
809 7326939466146358208061638398
810 7656888455647436383127772031
811 8001482128749658280120473144
812 8361361150999645348818606255
813 8737193813532983177238132589
814 9129677207214765818448043349
815 9539538446034726752974955628
816 9967535941663985823022807734
817 10414460731415553421995989803
818 10881137861677857160319696508
819 11368427829245614544586563325
820 11877228082793029988035476720
821 12408474587110515750561572755
822 12963143452540202519452671808
823 13542252632444184213170707035
824 14146863691346808886916061026
825 14778083646814839168293522513
826 15437066887939878357254655794
827 16125017173735266144587235448
828 16843189714553343420890074983
829 17592893340103644770385239060
830 18375492757439331814924246986
831 19192410902782346456398435550
832 20045131390837530765357135861
833 20935201065779392331214157508
834 21864232657867953013329064231
835 22833907550215690732507119647
836 23845978659993336269352446981
837 24902273438961990066246556909
838 26004696997977802042596045406
839 27155235360751413021708467497
840 28355958851896222838114610832
841 29609025624974014134776252833
842 30916685335991517038732231253
843 32281282968516875197475050511
844 33705262816323359278199249193
845 35191172630226516879536370892
846 36741667935512850356271796635
847 38359516527163148049720477324
848 40047603149799249685349528217
849 41808934370137149899879262446
850 43646643649449046460756089231
851 45563996624443240646955204120
852 47564396604684901809333814542
853 49651390295642474030421847679
854 51828673756153435904622500600
855 54100098600123859379067496731
856 56469678451980475807069799386
857 58941595666477391919470973648
858 61520208323159777877136864651
859 64210057506936961158301069949
860 67015874885914135403668110062
861 69942590598852917737486702358
862 72995341464325144068562926402
863 76179479524920745975491230379
864 79500580939562984240168386127
865 82964455238361009510193465840
866 86577154954121450213760940391
867 90344985646102796566936959664
868 94274516331288533419139510836
869 98372590340007884973013750267
870 102646336612426982213156268962
871 107103181454082849267910330099
872 111750860768329787024693164354
873 116597432785320210178874486933
874 121651291306844064511838945364
875 126921179488212955470651858267
876 132416204178083925522403312674
877 138145850839096420679171315862
878 144119999071913595432965767904
879 150348938767361854404820067768
880 156843386911091237971223424465
881 163614505067414202427163034111
882 170673917568722713118436406270
883 178033730439259297024488788768
884 185706551081776562474100260734
885 193705508758145368903829058629
886 202044275894750328574729975275
887 210737090246196726290887379270
888 219798777950654552348196221827
889 229244777513020912266998913672
890 239091164751910635960275262849
891 249354678749521784052825138903
892 260052748843282486968713469004
893 271203522701415623851515031019
894 282825895524453428312871678931
895 294939540418170073423873464438
896 307564939983336834375995749532
897 320723419171359838411582184186
898 334437179454843560361897996683
899 348729334366012554079146366849
900 363623946455959842705595632243
901 379146065731829095348859615447
902 395321769629133219419966119348
903 412178204580816582325548294367
904 429743629244830574336903123089
905 448047459456680313262711543808
906 467120314973637923901907048308
907 486994068082308249393677301377
908 507701894141554512222807952701
909 529278324138104311499040355514
910 551759299332571760502716425702
911 575182228079288371010167997115
912 599586044903855082537845184238
913 625011271928351522655920802564
914 651500082734774346609366282186
915 679096368763691607667856614289
916 707845808345864482047669022442
917 737795938471420394547510185191
918 768996229402068360148796184240
919 801498162239125707213582531219
920 835355309561189523514030779726
921 870623419253040070192805792457
922 907360501648601342122601415536
923 945626920119045401152916943243
924 985485485238556583494492579369
925 1027001552669074859295825740895
926 1070243124906977990129174034615
927 1115280957044043583699759736680
928 1162188666696904432116906345803
929 1211042848269209310453926174345
930 1261923191712828475713377472452
931 1314912605965100998434423119633
932 1370097347241527712409599808088
933 1427567152374675203166999164376
934 1487415377392769447554090102949
935 1549739141543570832624704976811
936 1614639476972171243642999366725
937 1682221484274269539187585017896
938 1752594494149898182457397332126
939 1825872235396346514558135632742
940 1902173009482844476894396683099
941 1981619871964258743779928243156
942 2064340820995310695465953568543
943 2150468993222491660127759621979
944 2240142867335587846924142040946
945 2333506475577437962941046990507
946 2430709623515806771491743273187
947 2531908118399084367056878892232
948 2637264006423351830711297258009
949 2746945819257372718933478847813
950 2861128830178522621042505225600
951 2979995320192961725867408336052
952 3103734854520485476971576801307
953 3232544569846142331931961234214
954 3366629472748575148489996355032
955 3506202749738151295273321526827
956 3651486089346616343670792584541
957 3802710016734669313347758254724
958 3960114241293399617944670816306
959 4123948017741850395041775697992
960 4294470521233463311432030876373
961 4471951237012260214244605431954
962 4656670365171137580939399120056
963 4848919241094648054928081708201
964 5049000772181282613081521312858
965 5257229891472294134337017699537
966 5473934028827956676037872237893
967 5699453600326350864925395400284
968 5934142516574936829208076206283
969 6178368710661690827193404141164
970 6432514686489181657549316596109
971 6696978088273956528724294562627
972 6972172292011755140886931476845
973 7258527019750714608759207395860
974 7556488977534555832611122900230
975 7866522517922219507885732866524
976 8189110328012066800449829006076
977 8524754143946267243899132278506
978 8873975492894613079586148869218
979 9237316463567746724863322718381
980 9615340506335537316615389275023
981 10008633264080554343316188238515
982 10417803434944643745494340517063
983 10843483668184528946944075110482
984 11286331494382913903526055841408
985 11747030291323444582071444589963
986 12226290286871141039272307347844
987 12724849600266029102881962311244
988 13243475323273877193446968310685
989 13782964642708592684561785653448
990 14344146005880166166256748397214
991 14927880330597548039701514852408
992 15535062261398588138734760178023
993 16166621473759849574013226466702
994 16823524028085541069214845474835
995 17506773775361037883215117893653
996 18217413816406876831581978207221
997 18956528016761268218388589205018
998 19725242579273883454319702123655
999 20524727676592179143940860583578
1000 21356199145780877408738760856292