0 1
1 0
2 1
3 0
4 0
5 1
6 1
7 2
8 2
9 2
10 4
11 4
12 6
13 9
14 10
15 12
16 19
17 21
18 24
19 36
20 44
21 49
22 66
23 81
24 100
25 123
26 144
27 180
28 229
29 265
30 317
31 391
32 473
33 566
34 675
35 798
36 968
37 1154
38 1354
39 1621
40 1926
41 2241
42 2675
43 3170
44 3691
45 4345
46 5113
47 5956
48 7002
49 8182
50 9503
51 11095
52 12919
53 14976
54 17446
55 20197
56 23327
57 27076
58 31300
59 36014
60 41607
61 47960
62 55151
63 63439
64 72831
65 83552
66 95953
67 109816
68 125595
69 143807
70 164316
71 187453
72 213963
73 243833
74 277801
75 316319
76 359448
77 408507
78 464415
79 526701
80 597131
81 677173
82 766800
83 867644
84 981753
85 1109534
86 1253382
87 1415211
88 1596386
89 1800306
90 2029361
91 2284740
92 2571903
93 2894248
94 3253649
95 3656174
96 4107154
97 4609798
98 5172481
99 5801165
100 6501091
101 7283042
102 8156025
103 9126886
104 10210044
105 11416667
106 12757696
107 14251457
108 15913675
109 17758828
110 19811648
111 22091978
112 24621398
113 27431379
114 30549574
115 34004581
116 37838255
117 42085566
118 46788120
119 52000538
120 57769499
121 64147593
122 71209275
123 79017737
124 87644666
125 97181853
126 107715696
127 119343952
128 132188709
129 146358142
130 161983602
131 179225563
132 198232233
133 219170484
134 242248793
135 267664622
136 295644655
137 326450605
138 360343349
139 397624299
140 438638242
141 483715263
142 533253801
143 587706066
144 647509634
145 713168847
146 785273425
147 864402351
148 951217219
149 1046461861
150 1150899560
151 1265395555
152 1390911537
153 1528421337
154 1679058565
155 1844067655
156 2024714200
157 2222440446
158 2438860605
159 2675622295
160 2934589688
161 3217806363
162 3527414966
163 3865824660
164 4235664114
165 4639664646
166 5080930900
167 5562833665
168 6088903277
169 6663090288
170 7289711844
171 7973299863
172 8718927128
173 9532073557
174 10418561648
175 11384869418
176 12437993687
177 13585340161
178 14835192110
179 16196458343
180 17678605097
181 19292125666
182 21048364268
183 22959377608
184 25038525970
185 27300165763
186 29759640811
187 32433870816
188 35341091547
189 38500757537
190 41934307516
191 45664767260
192 49716835183
193 54117599575
194 58896180016
195 64083768893
196 69714606027
197 75825399417
198 82455582940
199 89648273940
200 97449772419
201 105909753933
202 115082536345
203 125026320467
204 135803704311
205 147482935311
206 160137207790
207 173845100040
208 188692321308
209 204770747889
210 222179119140
211 241024690737
212 261422627606
213 283496752092
214 307381469509
215 333220714886
216 361169504236
217 391395913012
218 424080002481
219 459415333339
220 497611835799
221 538894337348
222 583504573824
223 631704083374
224 683773356086
225 740013834096
226 800751305281
227 866334757674
228 937139762261
229 1013571693849
230 1096064690821
231 1185085412876
232 1281137752923
233 1384761208681
234 1496535549842
235 1617085656755
236 1747081165415
237 1887241491935
238 2038341446207
239 2201210487962
240 2376740289458
241 2565890402720
242 2769687909041
243 2989235816157
244 3225721256480
245 3480414602191
246 3754679651824
247 4049982360153
248 4367892371915
249 4710094117808
250 5078397052003
251 5474737236553
252 5901192851241
253 6359994903850
254 6853530202990
255 7384358702664
256 7955228351539
257 8569078303185
258 9229060076619
259 9938553528339
260 10701174435009
261 11520798240896
262 12401579302629
263 13347959638181
264 14364700376671
265 15456902559990
266 16630019475684
267 17889892466722
268 19242779090132
269 20695367319294
270 22254818864457
271 23928800443490
272 25725506381774
273 27653708031749
274 29722792123529
275 31942787104181
276 34324425800136
277 36879188773028
278 39619339912176
279 42557997912147
280 45709192092284
281 49087904674993
282 52710158034564
283 56593078070589
284 60754952237237
285 65215330004432
286 69995101221208
287 75116564719726
288 80603553094776
289 86481523050010
290 92777643778396
291 99520940720784
292 106742409844586
293 114475122842887
294 122754401883911
295 131617952219584
296 141105997763643
297 151261482966414
298 162130237961413
299 173761140898034
300 186206362956579
301 199521559564684
302 213766076707228
303 229003237402029
304 245300577542494
305 262730089615271
306 281368570940099
307 301297901769768
308 322605349065076
309 345383971320638
310 369732962936194
311 395758016185568
312 423571808020263
313 453294405433367
314 485053717501080
315 518986063980009
316 555236668427821
317 593960195964610
318 635321443348252
319 679495921245101
320 726670510552807
321 777044270183983
322 830829153815024
323 888250790191814
324 949549449016338
325 1014980889256566
326 1084817318678446
327 1159348525694472
328 1238882905401970
329 1323748601070575
330 1414294870085409
331 1510893297584398
332 1613939174266417
333 1723853102526758
334 1841082481032650
335 1966103138982543
336 2099421244789161
337 2241575067350648
338 2393136970524001
339 2554715656362784
340 2726958277457839
341 2910552803766607
342 3106230721061508
343 3314769535718069
344 3536995612120569
345 3773787348557026
346 4026078212253524
347 4294860102384491
348 4581187124822801
349 4886179193211064
350 5211026087085430
351 5556991893966557
352 5925419318818063
353 6317734494234895
354 6735452297065642
355 7180181455773711
356 7653630286532660
357 8157612956555466
358 8694055638966031
359 9265003303525823
360 9872627136790139
361 10519231834624200
362 11207263752091628
363 11939319646374755
364 12718155364736991
365 13546695485054617
366 14428043742421935
367 15365493315310954
368 16362538281851665
369 17422885910433751
370 18550468976615624
371 19749459295240379
372 21024282268337244
373 22379631468929396
374 23820484781364035
375 25352121535594302
376 26980139838556860
377 28710475633836838
378 30549423055601061
379 32503654928184454
380 34580245355112511
381 36786693684366071
382 39130948927680838
383 41621436422355708
384 44267086160544503
385 47077361632657018
386 50062291478896066
387 53232502851577950
388 56599255601952390
389 60174479589576445
390 63970814189713417
391 68001648652341721
392 72281166199180121
393 76824390521220811
394 81647233669659927
395 86766547994720304
396 92200181001368458
397 97967031837909449
398 104087112744188036
399 110581613571963858
400 117472968557746024
401 124784928650322514
402 132542637693023337
403 140772711093978088
404 149503321138783923
405 158764286565559820
406 168587165547821280
407 179005355999413685
408 190054201111803912
409 201771098836880704
410 214195620150387601
411 227369633024037526
412 241337431547982718
413 256145874904390333
414 271844533374128742
415 288485840188043639
416 306125255081246161
417 324821435724703003
418 344636416682984201
419 365635801420877339
420 387888963893790526
421 411469258834826844
422 436454247552227310
423 462925934430761544
424 490971014368731497
425 520681137669033532
426 552153187915637588
427 585489572416128404
428 620798533337650028
429 658194473516595591
430 697798297806145899
431 739737777728382957
432 784147933912335538
433 831171436445927924
434 880959032710203737
435 933669995419873565
436 989472592639153024
437 1048544588800291745
438 1111073770045748418
439 1177258495009274226
440 1247308282128587886
441 1321444424583280662
442 1399900636077590195
443 1482923738122018052
444 1570774380541751490
445 1663727797481870983
446 1762074612058952799
447 1866121679143900745
448 1976192971077286691
449 2092630518499029326
450 2215795396593504283
451 2346068761058929035
452 2483852948886916399
453 2629572631085828257
454 2783676024776325803
455 2946636179226791695
456 3118952323965660139
457 3301151285246597579
458 3493788988864608287
459 3697452034622744488
460 3912759352489818732
461 4140363956886399797
462 4380954785761478632
463 4635258634378792202
464 4904042204144864627
465 5188114248735390389
466 5488327832177071986
467 5805582718657016825
468 6140827877938816413
469 6495064119721881230
470 6869346881355282351
471 7264789149262610380
472 7682564533145117214
473 8123910515092846167
474 8590131856132393422
475 9082604179744062637
476 9602777759767737329
477 10152181489396418536
478 10732427058028291144
479 11345213362822064846
480 11992331134152061255
481 12675667800284255128
482 13397212624665889079
483 14159062091061344641
484 14963425570353233990
485 15812631298900172488
486 16709132647279027445
487 17655514715042848663
488 18654501288764298381
489 19708962134646683814
490 20821920672060834651
491 21996562064638269725
492 23236241704528502517
493 24544494135357152282
494 25925042459552940969
495 27381808200837394720
496 28918921680210147666
497 30540732946858406236
498 32251823240749231562
499 34057017048717276644
500 35961394805863910172
501 37970306209992824242
502 40089384226885111388
503 42324559837885158992
504 44682077504987353323
505 47168511431331333783
506 49790782681129681739
507 52556177129668558819
508 55472364340820905058
509 58547417430550244862
510 61789833896706909954
511 65208557519474326100
512 68813001406049577591
513 72613072149634886086
514 76619195231077613386
515 80842341737080781542
516 85294056377369042745
517 89986486931943905727
518 94932415221090389548
519 100145289576913519427
520 105639258976163577469
521 111429208921010034635
522 117530799063559276544
523 123960502746215095819
524 130735648566151755648
525 137874463949698754901
526 145396120945088973623
527 153320784343832247358
528 161669662137347974016
529 170465058525771842827
530 179730429616801394378
531 189490441820045149398
532 199771033197263732262
533 210599477902297467486
534 222004453744496546355
535 234016113156462856730
536 246666157732395412141
537 259987916364695438913
538 274016427314838506908
539 288788524390531768981
540 304342927291570524211
541 320720336478841067420
542 337963532780919513041
543 356117481806808109607
544 375229443584925704829
545 395349087643063750214
546 416528613645415983066
547 438822878042012756070
548 462289526995633089156
549 486989135705567275823
550 512985354667074405475
551 540345063144968747575
552 569138530039886585886
553 599439582723927578301
554 631325784189470453726
555 664878618708869730209
556 700183686682842789541
557 737330909034236160849
558 776414741423614509822
559 817534399023727365187
560 860794092289889760445
561 906303274025779998387
562 954176898608669628182
563 1004535693842035716271
564 1057506445835641117505
565 1113222297846343046997
566 1171823063649963445545
567 1233455555891587258852
568 1298273930504792796380
569 1366440047807548478937
570 1438123850852634704791
571 1513503762222898638155
572 1592767100008205412012
573 1676110513605625536514
574 1763740440730419256362
575 1855873586436198357136
576 1952737424952208333917
577 2054570725852798730461
578 2161624105524542578123
579 2274160604834853988674
580 2392456294760704777131
581 2516800911030135231422
582 2647498518897553572240
583 2784868209979698280281
584 2929244832416741299672
585 3080979755616462120152
586 3240441671813717354767
587 3408017435831934802617
588 3584112944584893556270
589 3769154058774845835848
590 3963587568443772316860
591 4167882204102998452895
592 4382529696281677791490
593 4608045885327705701702
594 4844971883546127628753
595 5093875292802385569142
596 5355351479771115206529
597 5630024911180688071142
598 5918550552664542094736
599 6221615333635817178964
600 6539939680997299641224
601 6874279125683402327954
602 7225425984898828616241
603 7594211123213764756035
604 7981505797119982636631
605 8388223586252576398494
606 8815322415031886684999
607 9263806669813154175267
608 9734729415326115877690
609 10229194714654295742678
610 10748360058606458321108
611 11293438908693859543420
612 11865703358730308814132
613 12466486921573529226657
614 13097187445962245849000
615 13759270169088313508527
616 14454270912392992510873
617 15183799426169652125608
618 15949542889593589840153
619 16753269574488943204952
620 17596832679375404099487
621 18482174341292871609105
622 19411329834936618403398
623 20386431966437780711373
624 21409715670554469081013
625 22483522821926854212341
626 23610307268962651227581
627 24792640100222873194708
628 26033215155517697848676
629 27334854791400089194870
630 28700515912548158113201
631 30133296282634040294350
632 31636441125959038683981
633 33213350032877892018427
634 34867584184584411177240
635 36602873909945988589511
636 38423126589489193841215
637 40332434923999581799512
638 42335085582477490379326
639 44435568246466282098930
640 46638585070725780036387
641 48949060576962081140652
642 51372152000292934298431
643 53913260110761855006943
644 56578040529268572077998
645 59372415560218997158603
646 62302586566388849083243
647 65375046907839938444426
648 68596595470618539415364
649 71974350813895105587990
650 75515765960794495888506
651 79228643861926420855612
652 83121153564336646639526
653 87201847114530929487289
654 91479677228961547231590
655 95964015768631885722258
656 100664673050870234246746
657 105591918036099105391505
658 110756499431425056522758
659 116169667748385579381935
660 121843198358292080639874
661 127789415592261377329616
662 134021217928928700986352
663 140552104318848635434368
664 147396201699278859171713
665 154568293748146584757081
666 162083850933365396442129
667 169959061917781864525932
668 178210866375859374520531
669 186856989285708224100754
670 195915976765124434441343
671 205407233515075846667842
672 215351061943442872537758
673 225768703046416928043375
674 236682379120351991024421
675 248115338386242492332670
676 260091901614960846130653
677 272637510835849023752371
678 285778780222557153500444
679 299543549255258546142903
680 313960938253899939386798
681 329061406388739516767191
682 344876812280943412839646
683 361440477300339756866206
684 378787251681607026352484
685 396953583586109344357636
686 415977591231915185383558
687 435899138228899713756829
688 456759912263596628891400
689 478603507272773167788940
690 501475509261762926233347
691 525423585930453115809387
692 550497580265756135004754
693 576749608277058176441284
694 604234161059752433284640
695 633008211366572289032743
696 663131324887688985552439
697 694665776448470521808324
698 727676671330022022730179
699 762232071939387181918472
700 798403130066681514821375
701 836264224961608182038235
702 875893107487400905557314
703 917371050619614924444531
704 960783006554817352694936
705 1006217770720865852740901
706 1053768152992302076939296
707 1103531156410725253444575
708 1155608163741645009355024
709 1210105132210405681180241
710 1267132796758696014190369
711 1326806882195846356904492
712 1389248324633586518033343
713 1454583502590990919346815
714 1522944478194492765277267
715 1594469248911248511368513
716 1669302010255878460452743
717 1747593429950566678400414
718 1829500934035466291656838
719 1915189005427082389977813
720 2004829495469217473534252
721 2098601949037329793635411
722 2196693943762003109485438
723 2299301443986163907292856
724 2406629170091686740573004
725 2518890983835439660031807
726 2636310290391554036419341
727 2759120457816847550300830
728 2887565254666371655171717
729 3021899306545775838960501
730 3162388572412541603270565
731 3309310841447879575132475
732 3462956251390562403742571
733 3623627829248991121532979
734 3791642055324083990285729
735 3967329451548604143879655
736 4151035195180299908033773
737 4343119758903132176599109
738 4543959578475135853995490
739 4753947749092960615593362
740 4973494751668589871304954
741 5203029210302922164481969
742 5442998682280179370631608
743 5693870481933775555527317
744 5956132539837312979460640
745 6230294298814168138177835
746 6516887648296022937216132
747 6816467898669826539686153
748 7129614797302377593273876
749 7456933587971180815704701
750 7799056115555556328870911
751 8156641977892829364569171
752 8530379726756974438482477
753 8920988120050420586694532
754 9329217427362399984966465
755 9755850791103803711948268
756 10201705645581512265437537
757 10667635196440177171273378
758 11154529962972116169986670
759 11663319385959232622639163
760 12194973503790499230046988
761 12750504699677301580173708
762 13330969522975829501310747
763 13937470587709331609856155
764 14571158551481784322770801
765 15233234178174360822601242
766 15924950487917829082234820
767 16647614997941728954151052
768 17402592058129375668953293
769 18191305285215417106110546
770 19015240099695417882024499
771 19875946369761892748017012
772 20775041166711030149337058
773 21714211636409412696675816
774 22695217991689590666122841
775 23719896630682290270685110
776 24790163386268768635916723
777 25908016912137299460213159
778 27075542211094645798525832
779 28294914311476552841694695
780 29568402097843083128512985
781 30898372302323828472864949
782 32287293663209927681825463
783 33737741257758994385209217
784 35252401016392297640967164
785 36834074425718052585386435
786 38485683428234729733689725
787 40210275526799840679848904
788 42011029102251381073494115
789 43891258953022823275116937
790 45854422065867463059939970
791 47904123627141027418884671
792 50044123284605817827533557
793 52278341670018376793025272
794 54610867193155769441905252
795 57045963118494032125219555
796 59588074936103514439744570
797 62241838038758759599857710
798 65012085717894637235239739
799 67903857491425657608526902
800 70922407776950895008843661
801 74073214924554924009245013
802 77361990623867889528706480
803 80794689700607615075580058
804 84377520318604742434680264
805 88116954603807803980548005
806 92019739707417299079089236
807 96092909326146678825962274
808 100343795698185882726582727
809 104780042094163040730728217
810 109409615823361606730329920
811 114240821776088231687178905
812 119282316523918337978382217
813 124543123000594374365461913
814 130032645787095378698691607
815 135760687025319014034127607
816 141737462985999727733077160
817 147973621317306287942525304
818 154480259001627138158709168
819 161268941049347166119964002
820 168351719959366768487117887
821 175741155977292332761171969
822 183450338183691870340526680
823 191492906445860268498113173
824 199883074267889100663520583
825 208635652575438625905953857
826 217766074472825032305757439
827 227290421011535472448414045
828 237225448011089061062584516
829 247588613974507651252695143
830 258398109142378908822004344
831 269672885731478448729147123
832 281432689405463585059192799
833 293698092027055240195848525
834 306490525743364549428970118
835 319832318457740417426498242
836 333746730743683646670528214
837 348257994258832642367137798
838 363391351719002813604501759
839 379173098494672896685354731
840 395630625895078304707716407
841 412792466207266552807538502
842 430688339560217976078019412
843 449349202687184686233395526
844 468807299661909321862360868
845 489096214687432971215303587
846 510250927019638987072550221
847 532307868110475088276416198
848 555304981059253084238504799
849 579281782464211366523886576
850 604279426769722705481124694
851 630340773208373405997801259
852 657510455441394010389117857
853 685834954004479057479112516
854 715362671670394843220393125
855 746144011844474005591559806
856 778231460113144324299409998
857 811679669070480335708124456
858 846545546553055784885633532
859 882888347417891891165941153
860 920769769003768478865472673
861 960254050422004643883277998
862 1001408075827958261812625826
863 1044301481830580386756194696
864 1089006769203916718000182007
865 1135599419070176616443663041
866 1184158013730871798169793533
867 1234764362329784062557043457
868 1287503631538018074052423323
869 1342464481459039040511889831
870 1399739206959752227014826731
871 1459423884640932939821076474
872 1521618525668930486638953887
873 1586427234699594081807527852
874 1653958375133595110154903481
875 1724324740951904247664021682
876 1797643735390303760584768414
877 1874037556720985993826095587
878 1953633391420093545752636629
879 2036563615011277463013296242
880 2122966000885720097351917521
881 2212983937411076654284955521
882 2306766653654385375417228157
883 2404469454055573288608300802
884 2506253962401687912026730169
885 2612288375465943726779508117
886 2722747726688762329564178199
887 2837814160293008808015241181
888 2957677216241270961870821558
889 3082534126457626806226847935
890 3212590122753241038552414179
891 3348058756912493528143287721
892 3489162233412809864163252963
893 3636131755270146607323101151
894 3789207883521552775513706033
895 3948640910874611413540682398
896 4114691250074647272053787534
897 4287629837562187277099146752
898 4467738553013890891004170396
899 4655310655383624877449121096
900 4850651236084545918925465828
901 5054077689976176096412663104
902 5265920204846784119466825834
903 5486522270108253679409618462
904 5716241205446643888093548881
905 5955448710200923252300792053
906 6204531434272455608129705063
907 6463891571396857968645825434
908 6733947475642659821889822607
909 7015134302034619039079574377
910 7307904672232225406648096956
911 7612729366230425241236463572
912 7930098041087002911361195148
913 8260519977717498640389194838
914 8604524856839442444916418096
915 8962663565189253550910666591
916 9335509033176095865585972577
917 9723657105182465902623789718
918 10127727443767807629850173089
919 10548364469077123349574623335
920 10986238334807458689919236243
921 11442045942136834020612544000
922 11916511993071481594377405259
923 12410390084723882917772126679
924 12924463846091903753827319183
925 13459548118966511723006590382
926 14016490184658929725993881466
927 14596171038302344456450650768
928 15199506712547428480326976738
929 15827449652541410260159633959
930 16480990144152279167204385880
931 17161157797471234719985954078
932 17869023087705274862339306475
933 18605698955651700702970793745
934 19372342470026490524271406428
935 20170156554006129566296824740
936 21000391778431737322285647647
937 21864348224213705494452228003
938 22763377416572992933852446811
939 23698884333854478744311758168
940 24672329493747865090710982330
941 25685231119860532062550032823
942 26739167391697621808167412679
943 27835778781216189648077760143
944 28976770479241891537645809652
945 30163914915159969095325825445
946 31399054373417162217795464152
947 32684103710506446389657882358
948 34021053176244150571503926863
949 35411971343288148574989911093
950 36859008148996823727532105017
951 38364398053881595415547761340
952 39930463321061414614831356333
953 41559617421295548022908901366
954 43254368568341848321585394498
955 45017323389561075360474249740
956 46851190736875183860729094994
957 48758785643377518239055836767
958 50743033431086651193760916727
959 52806973975543910734417893468
960 54953766133166657857587144301
961 57186692337485223768826958213
962 59509163370623744079220231495
963 61924723316620891289595998756
964 64437054703427642793981044382
965 67049983840677516712397086396
966 69767486360587662854279327447
967 72593692969617692880066129676
968 75532895418801096307814940295
969 78589552700956492831585760712
970 81768297483285754603165422381
971 85073942784186122887657725386
972 88511488903429461842163535608
973 92086130615195527950761110915
974 95803264633802838278678045102
975 99668497362343199285501843545
976 103687652934798398973533223405
977 107866781562614038688924883975
978 112212168197109470852067101113
979 116730341519517302800931732705
980 121428083270887605108383130879
981 126312437934541114432436361478
982 131390722784218028507700621219
983 136670538311559811773620921744
984 142159779047061876241182490987
985 147866644789149416112679202757
986 153799652256575223922433865503
987 159967647179894597150069935519
988 166379816848345962103856302377
989 173045703129073160837136138394
990 179975215976244903764792117673
991 187178647448264833209790442898
992 194666686251941727367025380579
993 202450432833178019621184143786
994 210541415034445670442500177655
995 218951604340069507341242422905
996 227693432731104927599269770498
997 236779810172387437701092316930
998 246224142755167274676833900948
999 256040351519594441217315474647
1000 266242891982200122233015203782