0 1
1 0
2 0
3 0
4 0
5 0
6 1
7 1
8 2
9 3
10 5
11 7
12 11
13 14
14 20
15 26
16 35
17 44
18 59
19 73
20 94
21 117
22 148
23 181
24 228
25 277
26 344
27 418
28 514
29 621
30 762
31 917
32 1116
33 1342
34 1624
35 1945
36 2348
37 2803
38 3366
39 4012
40 4798
41 5700
42 6798
43 8052
44 9565
45 11305
46 13383
47 15771
48 18618
49 21880
50 25745
51 30187
52 35414
53 41414
54 48461
55 56531
56 65967
57 76783
58 89370
59 103779
60 120515
61 139636
62 161772
63 187060
64 216235
65 249521
66 287854
67 331515
68 381668
69 438759
70 504168
71 578532
72 663590
73 760151
74 870373
75 995400
76 1137820
77 1299176
78 1482706
79 1690366
80 1926163
81 2192719
82 2494877
83 2836065
84 3222307
85 3657922
86 4150345
87 4705194
88 5331495
89 6036444
90 6831213
91 7724813
92 8730992
93 9861240
94 11132284
95 12558636
96 14160905
97 15957144
98 17972642
99 20230106
100 22760310
101 25591624
102 28761811
103 32305956
104 36270250
105 40698363
106 45646459
107 51168636
108 57333542
109 64207713
110 71874851
111 80417094
112 89936043
113 100532733
114 112330894
115 125454167
116 140052920
117 156278757
118 174313803
119 194343436
120 216588658
121 241275264
122 268670972
123 299051069
124 332738998
125 370069628
126 411434114
127 457238587
128 507955372
129 564077162
130 626173077
131 694839706
132 770763050
133 854663775
134 947367670
135 1049745167
136 1162788546
137 1287547439
138 1425214158
139 1577051956
140 1744491763
141 1929053315
142 2132451306
143 2356511468
144 2603287928
145 2874970410
146 3174016942
147 3503052339
148 3865014029
149 4263044423
150 4700652249
151 5181594245
152 5710057215
153 6290529371
154 6928000733
155 7627827338
156 8395953140
157 9238761808
158 10163326760
159 11177251088
160 12288943268
161 13507449327
162 14842758500
163 16305621556
164 17907894847
165 19662345798
166 21583033053
167 23685104381
168 25985218694
169 28501329611
170 31253160251
171 34261974142
172 37551100942
173 41145701635
174 45073353135
175 49363800435
176 54049614213
177 59165932877
178 64751192402
179 70846867486
180 77498284585
181 84754354766
182 92668488517
183 101298325135
184 110706750422
185 120961635247
186 132136971504
187 144312612934
188 157575553964
189 172019680850
190 187747197825
191 204868406023
192 223503298584
193 243781362316
194 265843374876
195 289841242119
196 315940007135
197 344317748036
198 375167829663
199 408698860512
200 445137232070
201 484727155668
202 527733507885
203 574441982654
204 625162286756
205 680228413038
206 740002247840
207 804873998027
208 875266242198
209 951634562755
210 1034472104312
211 1124310428689
212 1221724666306
213 1327334645352
214 1441810688804
215 1565875092332
216 1700308658527
217 1845952561495
218 2003715738581
219 2174577220842
220 2359594466389
221 2559906266236
222 2776742152168
223 3011425947619
224 3265386419871
225 3540161597720
226 3837410799774
227 4158919879874
228 4506614824596
229 4882568045983
230 5289013789736
231 5728355660603
232 6203184044163
233 6716285102354
234 7270660490089
235 7869538016812
236 8516394002896
237 9214965887981
238 9969277536079
239 10783654140669
240 11662750888123
241 12611570471843
242 13635495608925
243 14740309585413
244 15932233091724
245 17217948315030
246 18604640690312
247 20100027026678
248 21712402885829
249 23450675373842
250 25324416843318
251 27343903109756
252 29520174346376
253 31865079472645
254 34391345267540
255 37112627869527
256 40043591142411
257 43199966402082
258 46598641299264
259 50257728906048
260 54196668594774
261 58436305875301
262 62999006797661
263 67908750174164
264 73191257342439
265 78874098473185
266 84986839827616
267 91561166200375
268 98631047916283
269 106232881797346
270 114405680562863
271 123191234851505
272 132634328101815
273 142782922637216
274 153688403311534
275 165405791138848
276 177994019560736
277 191516179361693
278 206039831991560
279 221637290161932
280 238385973009652
281 256368727435805
282 275674230682752
283 296397357909502
284 318639638561842
285 342509676583654
286 368123667527700
287 395605878738534
288 425089235237676
289 456715867904170
290 490637777300798
291 527017459134602
292 566028656073847
293 607857071090320
294 652701218823675
295 700773238473217
296 752299857857609
297 807523319274252
298 866702470743969
299 930113820114583
300 998052770075865
301 1070834817396321
302 1148796950531730
303 1232299013325794
304 1321725286037134
305 1417486035454950
306 1520019303091173
307 1629792666058580
308 1747305259321292
309 1873089775096499
310 2007714749004311
311 2151786829444394
312 2305953361563816
313 2470904961579792
314 2647378436907818
315 2836159705174769
316 3038087093143973
317 3254054645358362
318 3485015850195268
319 3731987388194486
320 3996053339788525
321 4278369430048854
322 4580167778842153
323 4902761706030804
324 5247551092762022
325 5616027818535776
326 6009781811052441
327 6430507195899013
328 6880009121281420
329 7360210711334878
330 7873160763178854
331 8421041605420478
332 9006177777188030
333 9631044906447883
334 10298279493365992
335 11010688937432846
336 11771262563009132
337 12583182939295923
338 13449838303019309
339 14374835333503544
340 15362013145458168
341 16415457701530408
342 17539517569779888
343 18738820177397554
344 20018289551342042
345 21383164642323705
346 22839019292514598
347 24391782887000170
348 26047762822585048
349 27813667773980034
350 29696632971048138
351 31704246402380574
352 33844577244114213
353 36126205362742983
354 38558253280516096
355 41150419381575685
356 43913013845341261
357 46856996009272706
358 49994014751815390
359 53336450519635202
360 56897460699855689
361 60691026878767835
362 64732005807576011
363 69036182527898416
364 73620327605338252
365 78502256832870915
366 83700895487196411
367 89236345403674996
368 95129957099876052
369 101404405110407249
370 108083768919733343
371 115193617550311746
372 122761100358381197
373 130815041983722848
374 139386044185995671
375 148506592395440038
376 158211169903005616
377 168536377396716446
378 179521060973099026
379 191206446203394293
380 203636281605004679
381 216856988962667087
382 230917824086623867
383 245871045314695553
384 261772093596689361
385 278679781324054850
386 296656494016236335
387 315768401874029786
388 336085685603418040
389 357682773365599425
390 380638593566909071
391 405036840183304120
392 430966255670199717
393 458520927982468228
394 487800607116320158
395 518911037526803274
396 551964312216727914
397 587079244673588120
398 624381764867523493
399 664005335301135525
400 706091393771456584
401 750789818649292178
402 798259423813008530
403 848668478851274555
404 902195262189695430
405 959028642557444427
406 1019368697004597168
407 1083427360690290491
408 1151429117245908198
409 1223611724734204441
410 1300226986653218927
411 1381541562800883800
412 1467837830141860274
413 1559414788293430500
414 1656589020512995857
415 1759695704604921547
416 1869089685434269812
417 1985146603263625934
418 2108264090466611926
419 2238863030643987322
420 2377388893624052121
421 2524313140188053810
422 2680134711010794321
423 2845381593474917116
424 3020612481935445824
425 3206418524929856206
426 3403425176076516229
427 3612294142006475092
428 3833725445339093877
429 4068459595907543905
430 4317279889611994307
431 4581014827997830923
432 4860540679407135880
433 5156784174716515981
434 5470725360108377682
435 5803400599828299664
436 6155905753102409129
437 6529399518153270903
438 6925106969348284441
439 7344323280446084365
440 7788417661998456145
441 8258837505942229023
442 8757112767626854547
443 9284860578449949555
444 9843790121707418196
445 10435707765033189772
446 11062522484604780793
447 11726251574760428388
448 12429026680986152820
449 13173100150289529679
450 13960851739924893631
451 14794795678956244543
452 15677588126896389846
453 16612035024482694367
454 17601100384376781222
455 18647915017566534582
456 19755785747098170313
457 20928205105779881318
458 22168861573669093620
459 23481650353003765285
460 24870684740930624895
461 26340308098913489033
462 27895106484095258594
463 29539921942929182233
464 31279866537717087452
465 33120337108029179688
466 35067030843470483892
467 37125961671713216541
468 39303477544583011288
469 41606278628361348117
470 44041436487988203040
471 46616414273894117827
472 49339088008644730691
473 52217768985090918886
474 55261227381353665454
475 58478717107720055644
476 61880001999668443573
477 65475383375938962059
478 69275729085542155939
479 73292504067009701754
480 77537802554300591266
481 82024381957638016248
482 86765698565175474718
483 91775945099375324801
484 97070090286508908231
485 102663920479521128025
486 108574083506285818763
487 114818134790659820642
488 121414585933233860308
489 128382955807233457401
490 135743824372679232728
491 143518889273330616755
492 151731025437182309811
493 160404347755212363215
494 169564277078445216970
495 179237609619411568281
496 189452590019113556640
497 200238988178352613284
498 211628180137470986945
499 223653233117644587516
500 236348995032851401280
501 249752188601581309649
502 263901510394775472077
503 278837734966872222036
504 294603824436297342591
505 311245043682127524539
506 328809081555895439484
507 347346178297352921820
508 366909259588788920058
509 387554077461343089438
510 409339358526797085391
511 432326959775664172854
512 456582032457576467629
513 482173194315189816171
514 509172710734046686490
515 537656685113422421727
516 567705259071304335779
517 599402822826040207723
518 632838236423260193200
519 668105062192181698681
520 705301809160492394782
521 744532189858053099363
522 785905390304798914481
523 829536353664179530312
524 875546078429902516280
525 924061931683863770421
526 975217978372138378387
527 1029155327199545210801
528 1086022494176093223908
529 1145975784485088592107
530 1209179693800752467927
531 1275807329801667700216
532 1346040855111246691475
533 1420071952496180979362
534 1498102313666999803445
535 1580344152605182998182
536 1667020744884487323675
537 1758366994014105695702
538 1854630026406365517895
539 1956069816110522871044
540 2062959841062962865362
541 2175587772121051412129
542 2294256196792401501523
543 2419283379065361579436
544 2551004057429003757239
545 2689770282641246853127
546 2835952297526336112227
547 2989939460528721678985
548 3152141215515595388916
549 3322988109740598711298
550 3502932862691691007519
551 3692451487940029006769
552 3892044470965060769520
553 4102238005297633231369
554 4323585290232161472829
555 4556667892697173760190
556 4802097176836857100719
557 5060515804165338342555
558 5332599308175979976833
559 5619057746567055739554
560 5920637435326587904308
561 6238122768167124381783
562 6572338125947344462907
563 6924149879933501729592
564 7294468493968370396521
565 7684250729798786242775
566 8094501961100474505289
567 8526278600888569285790
568 8980690648367400010359
569 9458904360388429838180
570 9962145054132663738351
571 10491700046714047336320
572 11048921738935398647664
573 11635230849472612026052
574 12252119807391099243211
575 12901156309906112185286
576 13583987054025749927727
577 14302341649686117730724
578 15058036723820667818760
579 15852980223738718464390
580 16689175930132951963089
581 17568728188930741548209
582 18493846873268213580909
583 19466852585722918468441
584 20490182113132177672492
585 21566394145142729709149
586 22698175269963977594057
587 23888346259577513527863
588 25139868659126363626871
589 26455851693949925608003
590 27839559510355062852423
591 29294418764918717734628
592 30824026579905841924458
593 32432158881054599532896
594 34122779136943758852070
595 35900047517789681330411
596 37768330494669610541910
597 39732210898765799787962
598 41796498463573193603226
599 43966240871578391008165
600 46246735330477724803377
601 48643540702536605924525
602 51162490214478830899976
603 53809704773800311805303
604 56591606921430127408183
605 59514935449142159567228
606 62586760714407035876925
607 65814500683832660023028
608 69205937740903969824847
609 72769236292173052547293
610 76512961210908073910520
611 80446097155636880146049
612 84578068806193408558197
613 88918762058294965898663
614 93478546223187754918848
615 98268297277316398000892
616 103299422212843165790206
617 108583884538266906380840
618 114134230984647077512127
619 119963619471376840929821
620 126085848392117400391525
621 132515387279967494192872
622 139267408918052254082420
623 146357822960211380351495
624 153803311134049833311356
625 161621364097156031875019
626 169830320025382726551763
627 178449405010686476744974
628 187498775354655143017996
629 196999561842527875969710
630 206973916091727355752763
631 217445059067690397258222
632 228437331869622375152445
633 239976248887676861955534
634 252088553443570595353815
635 264802276025650729256106
636 278146795240657501070682
637 292152901603586723161291
638 306852864299052846809696
639 322280501046894476628877
640 338471251217587278342858
641 355462252342579441047484
642 373292420178374786275144
643 392002532482980118149265
644 411635316677996043910315
645 432235541569698109582895
646 453850113318141156746826
647 476528175843703180823760
648 500321215877269816879340
649 525283172861003284275864
650 551470553924605629868177
651 578942554163135343314927
652 607761182461672158936262
653 637991393113733904573345
654 669701223500949285532687
655 702961938103617809970030
656 737848179133855609801490
657 774438124085734881101372
658 812813650520470815866692
659 853060508408071600614939
660 895268500372210591261752
661 939531670189172082744952
662 985948499918892556239153
663 1034622116051026673779705
664 1085660505078104174355692
665 1139176738913660522640743
666 1195289210604476853444006
667 1254121880792893861179393
668 1315804535418695540334797
669 1380473055158012075483081
670 1448269697132676360649367
671 1519343389432670560046838
672 1593850039032926277650612
673 1671952853696328163370706
674 1753822678496244611444137
675 1839638347604027173013395
676 1929587052031461472418342
677 2023864724031965169140573
678 2122676438912173920222729
679 2226236835021241873238683
680 2334770552736590555936128
681 2448512693282591671680489
682 2567709298273916476744157
683 2692617850895315299666386
684 2823507799688976415196506
685 2960661105943156119653561
686 3104372815739620605012945
687 3254951657742746977507920
688 3412720667881792850423145
689 3578017842106192462809709
690 3751196818467589396031072
691 3932627589814008845603114
692 4122697248461023750266706
693 4321810764240134727515053
694 4530391797410075963838119
695 4748883547956158122065777
696 4977749642894767734699727
697 5217475063243967305661282
698 5468567112420181008926616
699 5731556427869627458445446
700 6006998037849791066732432
701 6295472465330218665988240
702 6597586881096747516085095
703 6913976308203092447852545
704 7245304880037379818748062
705 7592267154337415081499432
706 7955589485621674204538780
707 8336031458576188531181730
708 8734387385080997192059401
709 9151487867640656206674257
710 9588201432137920663329361
711 10045436232918878021442564
712 10524141833384447918483160
713 11025311065361448670615597
714 11549981970706034702538312
715 12099239828700561034986427
716 12674219272998538779052037
717 13276106501991479754873204
718 13906141586680160106175661
719 14565620880263847520701974
720 15255899533886100377755989
721 15978394123119726804475206
722 16734585390016196379521199
723 17526021105702917410194787
724 18354319058773552609184611
725 19221170174890087610870904
726 20128341773297707262990428
727 21077680966143888252495756
728 22071118206797690183137191
729 23110670993573900057912875
730 24198447735595276848642154
731 25336651787754775419598664
732 26527585662094165080606453
733 27773655423165830508855822
734 29077375275327108832647452
735 30441372350190557901040863
736 31868391702866400091160555
737 33361301525933193626526966
738 34923098590518347595266913
739 36556913924197945913221095
740 38266018735906256902423327
741 40053830598403660112117568
742 41923919899370824282388605
743 43880016572588509078435848
744 45926017121222725478448219
745 48065991945662615275009246
746 50304192988963353832818634
747 52645061713413236569217682
748 55093237422397222692881917
749 57653565942238710423935599
750 60331108679406473152589380
751 63131152069029530183814261
752 66059217431424113048690658
753 69121071253943080906565974
754 72322735916280283870168896
755 75670500878023259498397825
756 79170934348135436333681896
757 82830895456769305730151375
758 86657546950770739122165390
759 90658368435019410856010357
760 94841170182785637051494745
761 99214107539138744158586789
762 103785695942560226174780250
763 108564826590845754913301655
764 113560782778587709328323807
765 118783256934543170243153182
766 124242368388496578991295502
767 129948681898329028740896188
768 135913226969414825527822721
769 142147517999665809178364560
770 148663575285065403327161147
771 155473946921839513273067750
772 162591731643054745435195637
773 170030602628853765101295810
774 177804832331312624841904078
775 185929318356448058918648590
776 194419610447819990059679055
777 203291938617851888376311995
778 212563242475062526591879050
779 222251201797225570912275957
780 232374268402710327939288570
781 242951699374237556430170734
782 254003591691700425487834269
783 265550918332852162859840281
784 277615565903271776448639577
785 290220373859355831872152883
786 303389175390903288363148480
787 317146840032397556045502787
788 331519318075134894851893660
789 346533686855102667036828836
790 362218198994799939341005529
791 378602332680182586128823592
792 395716844057467575487888046
793 413593821837775531309096347
794 432266744201427821999199063
795 451770538097234655163593048
796 472141641036255193899171933
797 493418065483329531213717643
798 515639465954158822221673237
799 538847208929851897144831103
800 563084445705691572843150411
801 588396188295365691551562013
802 614829388517129843268338462
803 642433020393239062741668992
804 671258165999625608718640612
805 701358104908079834177817203
806 732788407369282169443042789
807 765607031390757232777023774
808 799874423870399229161076463
809 835653625952420106818943348
810 873010382779675983629587710
811 912013257823048101946992320
812 952733751976226343379655549
813 995246427611524757356614311
814 1039629037800643188945326374
815 1085962660912176813371545498
816 1134331840806621546005134520
817 1184824732858166576667004283
818 1237533256042225482549640028
819 1292553251336909381675418513
820 1349984646697076478026956076
821 1409931628869610496910232722
822 1472502822329843158813193325
823 1537811475629882096106488711
824 1605975655461765912197660492
825 1677118448750109319664184091
826 1751368173102030282449964371
827 1828858595954859490803497524
828 1909729162776306780469996823
829 1994125234685512571927270070
830 2082198335878714595866012410
831 2174106411258142732509656267
832 2270014094679273960713527056
833 2370092988247681757971857393
834 2474521953114546454781620309
835 2583487412237313007836496046
836 2697183665591231342453381052
837 2815813218336357512241549967
838 2939587122465370734197476894
839 3068725332477941429694054517
840 3203457075649810618550373029
841 3344021237486780836291626366
842 3490666762978022034716214715
843 3643653074286927892355958566
844 3803250505543879073616302602
845 3969740755431036873659170384
846 4143417358277480213970415816
847 4324586174410854743880474897
848 4513565900542123054835683843
849 4710688600990115676701001733
850 4916300260585408395251715758
851 5130761360125595928616960427
852 5354447475289451921123247006
853 5587749899952636466336134102
854 5831076294885829389731065045
855 6084851362854173460430764718
856 6349517551178144569032541172
857 6625535782857030670317846970
858 6913386217400685646304819095
859 7213569042559589385048455371
860 7526605298191235078870579510
861 7853037733548790555619289499
862 8193431699329748959998942470
863 8548376075874051088705070456
864 8918484238957003482229136193
865 9304395064678226773243752907
866 9706773975008101094399310300
867 10126314025613554757370815075
868 10563737037650006830422158264
869 11019794775271473463421076721
870 11495270170680912182944187279
871 11990978598613275297825275769
872 12507769202219304013594772097
873 13046526272394096476094058731
874 13608170682675966021243671675
875 14193661381923150633815758243
876 14803996947063799458895689969
877 15440217198303222176033764776
878 16103404879267128056928245850
879 16794687404655165145710686215
880 17515238678081219389676819303
881 18266280982880088311522946078
882 19049086948770274447429647277
883 19864981597373959174139195774
884 20715344469713946080747782103
885 21601611838927473716941026596
886 22525279011564787682502694483
887 23487902720969951242165969290
888 24491103616379339652738803280
889 25536568851513066665607155826
890 26626054776583302249323752408
891 27761389737794249585952508907
892 28944476988568831749932419646
893 30177297716899805355448439834
894 31461914193395762636228049630
895 32800473044767925260739443964
896 34195208657689796879086567193
897 35648446718150945106117191119
898 37162607891626797210056201676
899 38740211649590361389756797149
900 40383880248107957395861454059
901 42096342864481034516710076679
902 43880439898129077565872006676
903 45739127442145791900454759477
904 47675481932211714520794946736
905 49692704979802107596783926542
906 51794128396899359790090489684
907 53983219419694771933025671344
908 56263586139055869501923751623
909 58638983145832508080422747067
910 61113317399388796554466087199
911 63690654328068105570843024432
912 66375224170636396097062041890
913 69171428568094235576370798873
914 72083847415611890642865675342
915 75117245984713812314126805913
916 78276582326230889484738585406
917 81567014964939615855422273504
918 84993910897229547187266244560
919 88562853903572239743445794608
920 92279653188019558109252370974
921 96150352357424467177107336867
922 100181238753567051835284188136
923 104378853151869693130707656001
924 108749999840912540539415764426
925 113301757097500301032724574512
926 118041488072599007911887613111
927 122976852104042951739723271960
928 128115816472523091945134410074
929 133466668617994588400817438142
930 139038028834299013966920452208
931 144838863460471330965379141940
932 150878498587909959121605705763
933 157166634303314639863139896046
934 163713359488059170753531818023
935 170529167195448243836646487134
936 177624970628128199715502669016
937 185012119738763672264551462356
938 192702418477975275315771456194
939 200708142714440183955663808432
940 209042058853007953815818082795
941 217717443177660034391337259636
942 226748101947164304012769497947
943 236148392272326713969049887502
944 245933243804842824757237623407
945 256118181268883049706250136287
946 266719347867729787637127062253
947 277753529599001974083166967849
948 289238180513276898551311268231
949 301191448952229290486611417240
950 313632204803778692143518472589
951 326580067813146072123790162026
952 340055436990195591873205781538
953 354079521154954643101044343529
954 368674370664791956809979744417
955 383862910368366104482754621523
956 399668973833163475150878233140
957 416117338895201284931902682673
958 433233764581306992406955442272
959 451045029456275196180568398198
960 469578971449177596283061052210
961 488864529215134495947946941707
962 508931785090979859198321283985
963 529812009705438722717218873248
964 551537708306719439660244723992
965 574142668872775388624360250513
966 597662012071946524081043545167
967 622132243144221002220587497335
968 647591305775997723216352696435
969 674078638043951426732923644728
970 701635230506441188455913720983
971 730303686523829107985898231337
972 760128284892128541120856085855
973 791155044877547570260313824314
974 823431793742775150005350446783
975 857008236859240473535955203724
976 891936030503104017438770986247
977 928268857436376167988089620231
978 966062505378351643685701352314
979 1005374948476458565950782839730
980 1046266431889697305167024094758
981 1088799559602048291761436137802
982 1133039385587609213473022273660
983 1179053508453741219835925924740
984 1226912169693212466982286461190
985 1276688355681184969952941699852
986 1328457903557951089146658949309
987 1382299611143547041509615157893
988 1438295351035808760988609980182
989 1496530189049046743645763273627
990 1557092507156359835181848093858
991 1620074131104638245517970219384
992 1685570462877584622437719862369
993 1753680618188562220585299715531
994 1824507569191824978660050052791
995 1898158292607647503347396916302
996 1974743923464120291412315103429
997 2054379914665857195769663307714
998 2137186202607647847390137715377
999 2223287379059125990596707421693
1000 2312812869554888253021688233758