Problem: The Travelling Salesman spends a lot of time travelling so he tends to get bored. To pass time, he likes to perform operations on numbers. One such operation is to take a positive integer x and reduce it to the number of bits set to 1 in the binary representation of x. For example for number 13 it's true that 1310 = 11012, so it has 3 bits set and 13 will be reduced to 3 in one operation.

He calls a number special if the minimum number of operations to reduce it to 1 is k.

He wants to find out how many special numbers exist which are not greater than n. Please help the Travelling Salesman, as he is about to reach his destination!

Since the answer can be large, output it modulo 109 + 7.

Input

The first line contains integer n (1 ≤ n < 21000).

The second line contains integer k (0 ≤ k ≤ 1000).

Note that n is given in its binary representation without any leading zeros.

Output

Output a single integer — the number of special numbers not greater than n, modulo 109 + 7.

Examples

Input

110
2


Output

3


Input

111111011
2


Output

169

Note

In the first sample, the three special numbers are 3, 5 and 6. They get reduced to 2 in one operation (since there are two set bits in each of 3, 5 and 6) and then to 1 in one more operation (since there is only one set bit in 2).

Solution (in PYTHON3):

Solution:
#l=[None,0,1,2,1,2,2,3,1,2,2,3,2,3,3,2,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,1,2,2,3,2,3,3,2,2,3,3,2,3,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,2,3,3,2,3,2,2,3,3,2,2,3,2,3,3,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,3,2,2,3,2,3,3,3,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,2,3,3,3,3,3,3,4,3,3,3,4,3,4,4,2,3,3,3,4,3,4,4,2,3,4,4,2,4,2,2,3,3,3,3,4,3,4,4,2,3]
ll=[[1],[2,4,8,16,32,64,128,256,512],[3,5,6,9,10,12,15,17,18,20,23,24,27,29,30,33,34,36,39,40,43,45,46,48,51,53,54,57,58,60,65,66,68,71,72,75,77,78,80,83,85,86,89,90,92,96,99,101,102,105,106,108,113,114,116,120,129,130,132,135,136,139,141,142,144,147,149,150,153,154,156,160,163,165,166,169,170,172,177,178,180,184,192,195,197,198,201,202,204,209,210,212,216,225,226,228,232,240,255,257,258,260,263,264,267,269,270,272,275,277,278,281,282,284,288,291,293,294,297,298,300,305,306,308,312,320,323,325,326,329,330,332,337,338,340,344,353,354,356,360,368,383,384,387,389,390,393,394,396,401,402,404,408,417,418,420,424,432,447,449,450,452,456,464,479,480,495,503,507,509,510,513,514,516,519,520,523,525,526,528,531,533,534,537,538,540,544,547,549,550,553,554,556,561,562,564,568,576,579,581,582,585,586,588,593,594,596,600,609,610,612,616,624,639,640,643,645,646,649,650,652,657,658,660,664,673,674,676,680,688,703,705,706,708,712,720,735,736,751,759,763,765,766,768,771,773,774,777,778,780,785,786,788,792,801,802,804,808,816,831,833,834,836,840,848,863,864,879,887,891,893,894,897,898,900,904,912,927,928,943,951,955,957,958,960,975,983,987,989,990,999],[7,11,13,14,19,21,22,25,26,28,31,35,37,38,41,42,44,47,49,50,52,55,56,59,61,62,63,67,69,70,73,74,76,79,81,82,84,87,88,91,93,94,95,97,98,100,103,104,107,109,110,111,112,115,117,118,119,121,122,123,124,125,126,131,133,134,137,138,140,143,145,146,148,151,152,155,157,158,159,161,162,164,167,168,171,173,174,175,176,179,181,182,183,185,186,187,188,189,190,193,194,196,199,200,203,205,206,207,208,211,213,214,215,217,218,219,220,221,222,224,227,229,230,231,233,234,235,236,237,238,241,242,243,244,245,246,248,249,250,252,259,261,262,265,266,268,271,273,274,276,279,280,283,285,286,287,289,290,292,295,296,299,301,302,303,304,307,309,310,311,313,314,315,316,317,318,321,322,324,327,328,331,333,334,335,336,339,341,342,343,345,346,347,348,349,350,352,355,357,358,359,361,362,363,364,365,366,369,370,371,372,373,374,376,377,378,380,385,386,388,391,392,395,397,398,399,400,403,405,406,407,409,410,411,412,413,414,416,419,421,422,423,425,426,427,428,429,430,433,434,435,436,437,438,440,441,442,444,448,451,453,454,455,457,458,459,460,461,462,465,466,467,468,469,470,472,473,474,476,481,482,483,484,485,486,488,489,490,492,496,497,498,500,504,511,515,517,518,521,522,524,527,529,530,532,535,536,539,541,542,543,545,546,548,551,552,555,557,558,559,560,563,565,566,567,569,570,571,572,573,574,577,578,580,583,584,587,589,590,591,592,595,597,598,599,601,602,603,604,605,606,608,611,613,614,615,617,618,619,620,621,622,625,626,627,628,629,630,632,633,634,636,641,642,644,647,648,651,653,654,655,656,659,661,662,663,665,666,667,668,669,670,672,675,677,678,679,681,682,683,684,685,686,689,690,691,692,693,694,696,697,698,700,704,707,709,710,711,713,714,715,716,717,718,721,722,723,724,725,726,728,729,730,732,737,738,739,740,741,742,744,745,746,748,752,753,754,756,760,767,769,770,772,775,776,779,781,782,783,784,787,789,790,791,793,794,795,796,797,798,800,803,805,806,807,809,810,811,812,813,814,817,818,819,820,821,822,824,825,826,828,832,835,837,838,839,841,842,843,844,845,846,849,850,851,852,853,854,856,857,858,860,865,866,867,868,869,870,872,873,874,876,880,881,882,884,888,895,896,899,901,902,903,905,906,907,908,909,910,913,914,915,916,917,918,920,921,922,924,929,930,931,932,933,934,936,937,938,940,944,945,946,948,952,959,961,962,963,964,965,966,968,969,970,972,976,977,978,980,984,991,992,993,994,996,1000],[127,191,223,239,247,251,253,254,319,351,367,375,379,381,382,415,431,439,443,445,446,463,471,475,477,478,487,491,493,494,499,501,502,505,506,508,575,607,623,631,635,637,638,671,687,695,699,701,702,719,727,731,733,734,743,747,749,750,755,757,758,761,762,764,799,815,823,827,829,830,847,855,859,861,862,871,875,877,878,883,885,886,889,890,892,911,919,923,925,926,935,939,941,942,947,949,950,953,954,956,967,971,973,974,979,981,982,985,986,988,995,997,998]]
facts=[1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,227020758,178290591,674358851,789741546,425606191,660911389,557316307,146326063,72847302,602640637,860734560,657629300,440732388,459042011,394134213,35757887,36978716,109361473,390205642,486580460,57155068,943272305,14530444,523095984,354551275,472948359,444985875,799434881,776829897,626855450,954784168,10503098,472639410,741412713,846397273,627068824,726372166,318608048,249010336,948537388,272481214,713985458,269199917,75195247,286129051,595484846,133605669,16340084,996745124,798197261,286427093,331333826,536698543,422103593,280940535,103956247,172980994,108669496,715534167,518459667,847555432,719101534,932614679,878715114,661063309,562937745,472081547,766523501,88403147,249058005,671814275,432398708,753889928,834533360,604401816,187359437,674989781,749079870,166267694,296627743,586379910,119711155,372559648,765725963,275417893,990953332,104379182,437918130,229730822,432543683,551999041,407899865,829485531,925465677,24826746,681288554,260451868,649705284,117286020,136034149,371858732,391895154,67942395,881317771,114178486,473061257,294289191,314702675,79023409,640855835,825267159,333127002,640874963,750244778,281086141,979025803,294327705,262601384,400781066,903100348,112345444,54289391,329067736,753211788,190014235,221964248,853030262,424235847,817254014,50069176,159892119,24464975,547421354,923517131,757017312,38561392,745647373,847105173,912880234,757794602,942573301,156287339,224537377,27830567,369398991,365040172,41386942,621910678,127618458,674190056,892978365,448450838,994387759,68366839,417262036,100021558,903643190,619341229,907349424,64099836,89271551,533249769,318708924,92770232,420330952,818908938,584698880,245797665,489377057,66623751,192146349,354927971,661674180,71396619,351167662,19519994,689278845,962979640,929109959,389110882,98399701,89541861,460662776,289903466,110982403,974515647,928612402,722479105,218299090,96415872,572421883,774063320,682979494,693774784,611379287,166890807,880178425,837467962,705738750,616613957,338771924,497191232,896114138,560652457,661582322,224945188,262995829,859081981,857116478,279856786,408062844,406076419,367193638,985761614,767884817,77737051,801784560,410447512,813374614,702909132,777826615,11426636,685259446,721228129,931065383,593559607,860745086,578819198,495425745,893029457,6156532,502193801,37480384,220174401,383076669,3013247,750298503,574624441,230733683,144887710,656590378,773954850,358485371,772254339,469363737,95843299,823414273,87709482,892174648,749756145,185864756,68295241,98238739,131504392,111672419,928208089,687974198,753032165,71715287,506557931,290314197,546089425,174590825,187067364,817659471,309331349,303445769,964814732,112937795,848457973,113604679,263728612,162653895,519013648,956915940,591788795,26960558,818561771,201473695,830318534,283328761,298655153,103269519,567777414,629890782,707451727,528064896,419467694,259775012,452053078,972081682,512829263,412924123,354780756,917691336,648929514,519218426,957710940,848100261,607279584,78508462,651656900,271922065,927371945,976904514,655633282,147015495,44958071,431540693,956102180,821001984,4640954,508310043,709072863,866824584,318461564,773853828,371761455,53040744,609526889,972452623,799173814,723225821,3874155,305590228,289496343,139259591,348260611,756867525,848691744,101266155,835557082,267191274,448180160,518514435,443022120,614718802,151579195,204297074,912569551,137049249,515433810,979001276,524451820,229298431,88837724,892742699,387369393,840349900,206661672,18186411,619853562,246548548,236767938,893832644,930410696,321544423,971435684,402636244,780681725,194281388,661238608,964476271,643075362,439409780,96895678,723461710,915447882,785640606,114709392,933696835,539582134,739120141,300372431,244129985,722433522,26638091,388855420,42468156,647517040,474194942,832805846,958306874,489519451,339220689,9833277,923477502,390998217,790283925,694135631,736657340,609563281,873127083,489593220,264439147,891171227,489029295,502009550,325923608,280525558,857054649,820622208,558213940,216997416,487921842,951328535,606653379,794417402,449723904,783486165,414645478,809681447,114612567,824953206,255016498,147060381,88903008,228293174,394357308,362355866,900088886,638573794,779598451,904922263,451026166,549459329,212643744,563246709,391796933,174243175,189725986,238337196,60051478,782959006,982673239,237607992,685987666,694447544,195840153,519748540,446086975,523485236,185780714,716004996,214280883,140643728,555470704,516522055,116665689,899547947,490696549,683197147,686671136,988747143,744912554,619072836,345158054,224284246,637879131,78947725,342273666,237716550,915360466,711578771,423071394,228124918,271834959,480779410,254894593,859192972,990202578,258044399,151532640,644862529,48049425,448119239,130306338,850105179,401639970,606863861,183881380,837401090,513536652,714177614,946271680,243293343,403377310,688653593,15447678,754734307,631353768,202296846,159906516,912696536,737140518,467380526,896686075,309895051,356369955,461415686,706245266,10064183,183054210,455971702,737368289,956771035,564163693,365118309,226637659,304857172,440299843,717116122,485961418,615704083,476049473,354119987,329471814,620060202,251964959,45357250,175414082,671119137,48735782,122378970,717506435,18459328,949577729,771970076,635808197,608040366,165916428,258536202,902229110,617090616,548564593,613394864,753777984,577888302,416452176,881599549,524547188,599140122,522765386,657552586,256787840,287613719,776067801,597965522,458655497,764387515,350167935,494713961,513386012,576480762,864589772,86987059,495636228,512647986,721997962,982831380,162376799,204281975,462134806,189646394,425968575,209834628,494248765,664281698,947663843,540352769,25662122,986679150,207298711,477043799,24708053,528335066,189351697,717500453,42764755,316734785,823726196,293357001,547414377,258966410,602945692,561521296,351253952,752369730,174204566,871148004,302242737,554611874,540181425,349941261,414343943,921115587,959388563,227019335,708812719,793380997,342547759,324322556,458370547,356254978,809319893,159690374,848340820,971304725,180230004,103061704,207441144,443272953,45593686,541647240,612817107,849140508,109375794,906749744,159084460,541378020,692284266,908221578,720697998,363923522,819281897,701846632,479994712,196613531,29272489,792937812,859009553,202148261,385627435,115321267,612859231,132778909,173511339,782369566,322583903,324703286,31244274,433755056,109559692,871157455,350443931,592104988,197184362,141678010,649163959,746537855,954594407,850681817,703404350,467293824,684978431,565588709,378843675,825260479,749777538,850502015,387852091,412307507,307565279,914127155,864079609,845970807,414173935,638273833,664477235,173471099,480759791,839694748,190898355,956270620,957911348,43002811,628936576,966234409,667971950,236586166,954211897,223051884,21058295,656573222,631532535,809706350,984734695,314281677,311454037,640732448,434907794,175084834,434807109,973816812,488481268,844735329,917344075,314288693,459259162,992521062,667512257,603748166,679935673,833938466,933875943,522922384,981191471,457854178,112860028,484939649,611363777,627371454,844300972,962501388,738504183,631041465,29224765,334078303,211237785,626057542,900175080,728504100,450509755,575177363,905713570,416609984,874776027,334255451,683287462,999293262,474888472,317020697,180417613,591538360,879151833,605566485,569294094,970567518,896200922,943088633,145735679,884701203,949403596,749113557,78958680,850679027,665376978,686499745,426302291,842343474,708066168,962548572,349652428,833757979,492365420,136639914,76093131,591710464,208764552,166233017,498121245,545840935,26721664,736011124,880639351,137410283,42609708,235572009,981737748,718913567,909319027,906112184,298059463,274736280,217450848,351267027,149682364,249066734,11785215,333890217,774940233,302540697,519852435,802535369,620684620,306323295,752310997,848793393,883503040,569433124,254795373,855478464,660158704,87911700,944741410,351053939,2634663,134077016,736459220,4882454,969435081,120150411,922584286,828772112,106810765,371205161,17024731,960279329,389323593,23991206,744762405,684217429,479374977,963728237,3246420,688035746,381629444,752436308,274567573,440219140,702541058,919238277,563955926,467150839,5249506,399086000,833151662,847391187,655983283,337920422,866913758,675206635,549602585,963783662,324756002,393087771,731515248,787956453,550936813,398161393,631665856,442637251,454846959,348994181,88011024,513458067,60476466,9760396,403700900,990173371,519613195,945797344,114696834,327457551,905694736,143025346,289024806,451579463,325709522,18701196,326143996,49850509,619195074,414881030,850660769,880149960,651809429,592293509,810577782,929598726,835669318,731671946,529667681,285562083,293565850,686472980,274474950,282703792,889076915,56602629,546147347,255724802,873696194,831784350,110556728,279941051,667003092,302778600,803516696,772054724,165410893,531446229,958833885,703493734,68812272,481542542,722167619,172528691,173636402,356397518,390931659,311533827,53449710,959934024,259493848,215350798,907381983,791418522,896453666,530274270,443147787,468552325,410897594,491169384,314015783,406644587,772818684,721371094,596483817,922913559,78344520,173781169,485391881,326797438,209197264,227032260,183290649,293208856,909531571,778733890,346053132,674154326,75833611,738595509,449942130,545136258,334305223,589959631,51605154,128106265,85269691,347284647,656835568,934798619,602272125,976691718,647351010,456965253,143605060,148066754,588283108,104912143,240217288,49898584,251930392,868617755,690598708,880742077,200550782,935358746,104053488,348096605,394187502,726999264,278275958,153885020,653433530,364854920,922674021,65882280,762280792,84294078,29666249,250921311,659332228,420236707,614100318,959310571,676769211,355052615,567244231,840761673,557858783,627343983,461946676,22779421,756641425,641419708]
facts_inv=[1,1,500000004,166666668,41666667,808333339,301388891,900198419,487524805,831947206,283194722,571199524,380933296,490841026,320774361,821384963,738836565,514049213,639669405,402087866,120104394,862862120,130130097,179570875,799148792,791965957,761229465,917082579,282752951,699405279,123313510,649139150,957785605,604781386,958964165,170256120,671396008,261389083,243720767,211377457,230284438,469031331,654024560,317535457,393580354,297635121,202122504,366002609,861791727,854322286,57086446,138374245,98814890,662241795,956708188,762849245,960050886,16842998,379600744,752196628,279203279,250478744,971781922,888440989,92006891,262953954,367620517,856233148,659650492,328400734,261834298,102279357,626420551,159266036,785936033,757145819,470488764,58058296,590487931,361904913,517023815,623666965,775898383,33444559,512302915,711909451,833859418,262458156,412073391,746203077,108291146,902288920,444590100,843490222,455781814,720587182,986672790,267903845,992529638,545379091,875453797,751242122,732855320,463425783,917917562,427789694,494601793,929856098,360461633,462022587,631472937,708391653,979539218,150261410,966230370,704054182,781931507,664802838,73430533,244314544,735369293,204424541,157413317,90710678,403957347,35231659,341549460,435760235,26841877,287029784,832977158,494908226,18900820,428713543,234542640,890626248,477136961,324650637,415396022,556945299,311121040,775256183,97008847,909769299,860484515,247313688,97584341,197942752,622959077,816261476,218775078,61051491,388559552,270513463,930328016,535034378,939327150,802161325,87355452,76021104,300475134,921120970,141488402,117432445,836081911,411127772,279585109,331015482,251970332,113916985,971258342,929656488,889125916,178549862,909072132,142337556,23536009,73579300,595918989,327351505,474040845,682177026,267484491,181789534,164031466,579265039,169780996,589143218,907389066,354007352,970284256,753771127,915384231,880390598,520002017,689846169,600458403,815230759,706137534,732191651,538660962,47456025,599244836,111326330,657408467,412962971,375791085,784424117,527809735,930755077,237765502,688330647,526831752,551769167,745569020,26723577,264012611,623336468,599189621,669402697,589406380,862395510,571452236,262652254,206529699,414251246,621302001,764851556,933179180,287917815,979512693,56188367,340759435,756827299,7507809,544712803,794680992,674239165,82664871,130052992,267208556,113141945,12864223,559723725,842457890,921805957,885861006,35975146,40467642,554379392,778217523,182383338,405485651,139942632,890314741,678001239,811242198,707436745,425222626,905116696,126558142,441097927,852828624,326436613,232297110,604650182,671446058,10005416,522425397,518670730,38958040,830402065,800847072,376559882,110863358,113130413,279395402,246496014,986498194,953356631,314119133,22470175,961072596,215410152,155688065,70721713,297450078,812883107,541016959,1872031,644834046,476442732,755056316,91314186,326841207,285853701,396235995,476081606,270053967,311939982,581039804,985319076,135712978,964144274,904487323,678375373,515288812,705261532,807484621,122354320,419749533,972410777,211450036,949557355,18947635,222282375,48171780,378700860,623832397,478444619,510870143,876980910,810176965,748638324,113421724,440348993,863313960,855851119,438584915,828080811,720691159,71663720,48408626,843989221,837856261,23396586,696498209,699396142,558282241,447074582,748373754,670816350,949329879,230172975,253576086,513778485,518825953,716192587,608379868,932975307,856951364,238908695,952383270,413462845,749755550,255633116,371504590,575270325,736243777,7621849,202798951,842667039,502327813,12403107,546737375,494648599,151624724,395508517,384226928,242233679,35789821,275029085,239986639,890723831,812542048,364833448,745651158,442296160,329212426,335960985,66673582,971303612,458040065,136966163,279002518,756568843,351700958,866541869,396563255,517728958,965430081,680218496,838469951,144627151,576509210,798927877,640906388,538138307,199844570,847618664,622119051,373122494,767097325,617288087,395092300,433074305,67569149,815890839,568176207,776450314,850674275,408395804,136913583,801784300,794207214,262154718,34284026,400561835,433972639,573828101,184699592,812790266,404769648,582517190,392883298,497395023,656097176,460552924,608552698,486267026,331363414,476406879,202491684,432338321,344314146,993894982,649068571,532377735,925873015,756095388,83536581,782502356,467833719,201958994,113067476,982276563,417000623,683259514,595275137,339855849,540755239,602085936,629650637,694546695,783468170,990732904,300418276,153830238,781995268,886235290,762796169,704474617,834858176,120593647,291208178,185572492,867351020,704212748,633983365,436319797,679651749,574691409,884692149,583265738,954817023,25168036,437027667,13494817,926806481,260807531,473460019,215121540,398786562,665421923,247242609,357210812,375220601,951489166,260146496,562904189,803189606,115688778,402674167,664102792,62073083,931438538,989781133,54305395,845490579,408508000,817016,770460718,252530800,193344993,18240764,451521272,550299453,675641621,648967803,128976362,498292114,586102337,268722858,813389329,711699206,345071263,549118359,498160774,12544712,899831499,7499676,159323417,860458480,925163407,526574743,431479193,124394448,736478932,827152428,468482333,191449968,570982019,630772527,6811956,460686917,587776989,189529436,618602480,213045731,31935150,166725807,46518902,361709447,728106284,141044314,106680816,648547039,81624401,345039463,428679492,444415784,871949944,552304261,263204892,812749473,93356306,615275825,658196191,99745872,808765204,980015659,506203240,798053748,875307384,490913669,395559142,537801345,254916759,26857248,323421544,786532324,111710215,362083412,98363148,686582519,232498406,816375871,302974657,320593384,541140925,837139904,84057040,831759554,589762885,489023570,342716282,966455154,672855976,456926629,511811424,370359005,435482844,480465346,749545478,742002607,688642026,635383632,287496457,895129599,639223927,732732045,883082755,597812434,281256739,243843142,932634458,133552203,978803223,605228299,76527469,923076281,353392926,363322540,770576388,900277818,11219964,45472760,708339507,491437446,743928014,675393437,584018351,629556304,639854830,305512590,408488823,110876181,497784495,617034693,851537422,102938949,385266150,668331122,814641919,630622468,978945869,28268783,357972167,146329111,973624935,149958790,433931296,25598024,447940280,354732829,764891064,685394573,585294277,465409408,469130064,920721745,182673921,284022508,597678446,416816025,588422624,98457962,240636924,36839874,300511140,182273503,581213731,455560749,864940520,856724314,261438685,740632796,674273817,942626165,174802133,374887767,194299387,742848665,907493095,441999251,492506669,611675310,290416066,970929824,883609623,223358251,807963821,422005815,659475855,461490465,664907290,263359925,173600234,665950005,716496304,824226812,899890349,390028746,771125588,145203352,452007490,325362082,146808268,736600017,245688986,146065271,957412368,898799739,278661168,704941285,610928999,81601883,483849511,959722958,846205539,512459448,477514011,94771790,785546670,950680044,61469483,942823288,676349828,399270685,202224300,83614201,27855221,178708942,736070142,898806733,147446631,252269212,554679879,911476215,87670064,942585856,185967971,834953514,366759830,422843000,170643325,93981853,572719111,985870900,598086433,218375794,859943833,859649526,91331965,695015236,607644320,732718027,917982226,747216559,979635810,561306185,34036360,223449518,94586255,423202372,442944642,611697021,200279654,277309078,618283679,820550379,353246455,521460957,68835467,668938271,630939793,166620027,751195077,59571869,663276431,490471791,292464946,386389206,728831039,100424847,231097324,77617394,253639149,723976405,560621283,219949516,322944880,693507607,78791198,119998459,265121019,385833490,175839688,127126701,357575575,462477947,523972795,85257542,474256318,882209397,465260644,945308123,444097002,744917420,375150087,199218939,962795536,153320195,574288074,366385933,970641480,460261345,165378268,54660122,796112070,75056929,684432874,318576890,508386937,736496795,933419021,301388996,795962538,981413164,518902828,825023058,764707707,274652931,632168477,715573025,516018880,296024238,427201967,100757491,425935778,453525227,714143838,325377579,154052075,164453301,661274799,281891479,854578132,707463702,54478503,560779145,542878457,842687510,21165703,595996646,257510057,793448599,603061927,924060221,392136705,100461338,471328395,891398279,205030949,652464912,835850842,87425060,823905986,380913646,278673941,927068232,520240501,876473603,136589194,511732167,687296805,683241687,350269024,968145478,892943787,218267753,631708693,575265725,844874308,490669196,539989340,283721451,422216333,634877244,154305891,30857166,70409600,192823595,593649861,218997343,408157062,510618691,46798894,349151803,787794327,112121118,212247051,734542883,558493333,135971470,553224553,555304942,877988083,353984399,287379295,128097089,213238733,686489183,584370424,478522537,386164116,728903056,854166382,496535429,200766267,471649197,622910706,125683017,956326056,20739963,301662013,197927580,561829805,470110929,409651919,25445274,530972257,693634465,812235796,433779479,246955439,273484835,533196859,434841810,150091327,794785050,966482053,130865325,820075960,424860898,894572050,601383094,45465724,85336318,672082365,48587322,356055887,859189025,162098823,439790362,893587086,428005909,694221764,21829348,71677376,928496509,456286540,290395261,680262749,924193154,292067220,171853628,296940288,150623112,455840069,180683168,811842548,508120422,642272196,544234726,650304911,229451663,921643700,798472778,749018037,226545381,765423842,718894474,717080061,749196186,489999179,806854513,378512648,701818525,88561613,592947516,719258871,280773178,426531817,513644853,265496088,511425456,854621511,704306302,284837521,431600849,280960245,932742910,291976581,677356118,77062670,110519140,832608350,207247104,180387636,52180388]

import sys
sys.setrecursionlimit(10000)
mod=1000000007

def combi(n,r):
    if r==0 or r==n:
        return 1
    if r<0 or n<r:
        return 0
    return (((facts[n]*facts_inv[r])%mod)*facts_inv[n-r])%mod

def solve(n,m,first_time=True):
    if n=="1":
        return 1 if (m==0 or m==1) else 0
    if m<0 or len(n)<m:
        return 0
    if m==0:
        return 1
    ind=n.find("1",1)
    if ind==-1:
        if first_time:
            return combi(len(n)-1,m)%mod
        else:
            return len(n) if m==1 else combi(len(n)-1,m)%mod
    else:
        if first_time and m==1:
            return (solve(n[ind:],m-1,False)+combi(len(n)-1,m)-1)%mod
        return (solve(n[ind:],m-1,False)+combi(len(n)-1,m))%mod

n=input()
k=int(input())
if k>5:
    print(0)
elif k==0:
    print(1)
elif k==1 and n=="1":
    print(0)
else:
    res=0
    for m in ll[k-1]:
        res+=solve(n,m)
        res%=mod
    print(res)