fork download
  1. // coding in the memory of Legend :)
  2.  
  3.  
  4. //~ mail ID : neernpatel@gmail.com
  5. //~ Author : DrexDelta
  6. //~ codechef : drexdelta , hackerRank : drexdelta , codeforces : drexdelta1
  7. //~ Contact Info : neernpatel@gmail.com
  8.  
  9.  
  10. #include<iostream>
  11. #include <cctype>
  12. #include <cerrno>
  13. #include <cfloat>
  14. #include <ciso646>
  15. #include <climits>
  16. #include <clocale>
  17. #include <cmath>
  18. #include <csetjmp>
  19. #include <csignal>
  20. #include <cstdarg>
  21. #include <cstddef>
  22. #include <cstdio>
  23. #include <cstdlib>
  24. #include <cstring>
  25. #include <ctime>
  26. #include <ccomplex>
  27. #include <cfenv>
  28. #include <cinttypes>
  29. #include <cstdbool>
  30. #include <cstdint>
  31. #include <ctgmath>
  32. #include <cwchar>
  33. #include <cwctype>
  34. #include <algorithm>
  35. #include <bitset>
  36. #include <complex>
  37. #include <deque>
  38. #include <exception>
  39. #include <fstream>
  40. #include <functional>
  41. #include <iomanip>
  42. #include <ios>
  43. #include <iosfwd>
  44. #include <iostream>
  45. #include <istream>
  46. #include <iterator>
  47. #include <limits>
  48. #include <list>
  49. #include <locale>
  50. #include <map>
  51. #include <memory>
  52. #include <new>
  53. #include <numeric>
  54. #include <ostream>
  55. #include <queue>
  56. #include <set>
  57. #include <sstream>
  58. #include <stack>
  59. #include <stdexcept>
  60. #include <streambuf>
  61. #include <string>
  62. #include <typeinfo>
  63. #include <utility>
  64. #include <valarray>
  65. #include <vector>
  66. #include <array>
  67. #include <unordered_map>
  68. #include <unordered_set>
  69.  
  70.  
  71. using namespace std;
  72.  
  73. #define F first
  74. #define S second
  75. #define MP make_pair
  76. #define PB push_back
  77. #define UB upper_bound
  78. #define LB lower_bound
  79. #define ER erase
  80. #define EN end()
  81. #define B begin()
  82. #define I insert
  83. #define OPTIMIZE ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  84. #define int ll
  85. #define endl "\n"
  86. #define CO cout <<
  87. #define CI cin >>
  88. #define NL cout << endl;
  89. #define DBG {int debug ; cin >> debug;}
  90. #define AND &&
  91. #define OR ||
  92. #define XOR ^
  93. #define OFLUSH fflush(stdout);
  94. #define IFLUSH fflush(stdin);
  95. #define LEN(x) ((int)x.length())
  96.  
  97. #define rep(i,x) for(int i = 0 ; i < x ; i++)
  98. #define rep1(i,x) for(int i = 1 ; i <= x ; i++)
  99.  
  100. #define repl(var,start_val,limit_val) for(int var = start_val ; var <= limit_val ; var++)
  101. #define perl(var,start_val,limit_val) for(int var = start_val ; var >= limit_val ; var--)
  102.  
  103. #define y1 qwert
  104. #define y2 trewq
  105. #define x1 asdfg
  106. #define x2 gfdsa
  107.  
  108. typedef long long ll;
  109. typedef pair<int,int> ii;
  110. typedef vector<int> vi;
  111. typedef set<int> si;
  112. typedef multiset<int> msi;
  113. typedef long double ld;
  114.  
  115. const ll maxn = 2e6+6 ;
  116. const ll MOD = 1e9 + 7;
  117.  
  118. bool comparator(int i , int j)
  119. {
  120. return (i < j);
  121. }
  122.  
  123. ll power(ll x, ll i)
  124. {
  125. ll ans = 1;
  126. while(i > 0)
  127. {
  128. if(i&1)
  129. ans = (ans*x)%MOD;
  130. i >>=1;
  131. x = (x*x)%MOD;
  132. }
  133. return ans;
  134. }
  135.  
  136. ll power(ll x, ll i,ll mod)
  137. {
  138. ll ans = 1;
  139. while(i > 0)
  140. {
  141. if(i&1)
  142. ans = (ans*x)%mod;
  143. i >>=1;
  144. x = (x*x)%mod;
  145. }
  146. return ans;
  147. }
  148.  
  149. ll modInverse(ll x, ll mod)
  150. {
  151. return power(x , mod-2,mod);
  152. }
  153.  
  154. bool isPalindrome(string s)
  155. {
  156. int limit = s.length()/2;
  157. for(int i = 0 ; i < limit ; i++)
  158. {
  159. if(s[i] != s[s.length()-i-1])
  160. return 0;
  161. }
  162. return true;
  163. }
  164.  
  165. ll gcd(ll x, ll y)
  166. {
  167. ll t;
  168. while(y != 0)
  169. {
  170. t = x%y;
  171. x = y;
  172. y = t;
  173. }
  174. return x;
  175. }
  176.  
  177. bool isVowel(char ch){
  178.  
  179. if(ch == 'a' || ch == 'i' || ch == 'e' || ch == 'u' || ch == 'o' || ch == 'y'){
  180. return true;
  181. }
  182. return false;
  183. }
  184.  
  185. bool isPrime(int n)
  186. {
  187. int root = sqrt(n);
  188. for(int i = 2 ; i <= root ; i++) if(n%i == 0) return 0;
  189. return 1;
  190. }
  191.  
  192. // Geometry
  193. ///////////////
  194.  
  195. ld getDis(ld x1 ,ld y1,ld x2,ld y2){
  196. return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
  197. }
  198.  
  199. ld getDisSquare(ld x1,ld y1,ld x2,ld y2){
  200. return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
  201. }
  202.  
  203. /////////////
  204. bool isSquareHelper(int x1 , int y1 , int x2 , int y2 , int x3 , int y3 , int x4 , int y4){
  205.  
  206. ld d1,d2,d3,d4,d5,d6;
  207. d1 = getDisSquare(x1,y1,x2,y2);
  208. d2 = getDisSquare(x2,y2,x3,y3);
  209. d3 = getDisSquare(x3,y3,x4,y4);
  210. d4 = getDisSquare(x4,y4,x1,y1);
  211.  
  212. if(d1 == d2 && d1 == d3 && d1 == d4){
  213.  
  214.  
  215. d5 = getDisSquare(x1,y1,x3,y3);
  216. d6 = getDisSquare(x2,y2,x4,y4);
  217. if(d5 == d6){
  218. return 1;
  219. }
  220.  
  221. }
  222. return 0;
  223.  
  224. }
  225.  
  226. // pass 4 points in any order,
  227. // returns 1 if it forms square, else returns zero
  228.  
  229. bool isSquare(int x1 ,int y1 , int x2 , int y2 , int x3 , int y3 ,int x4 , int y4){
  230.  
  231. if( isSquareHelper(x1,y1,x2,y2,x3,y3,x4,y4) ||
  232. isSquareHelper(x1,y1,x2,y2,x4,y4,x3,y3) ||
  233. isSquareHelper(x1,y1,x3,y3,x2,y2,x4,y4) )
  234. return 1;
  235. else
  236. return 0;
  237.  
  238. }
  239.  
  240. ////////
  241. bool isEqualateralTriangle(int x1, int y1,int x2, int y2, int x3, int y3){
  242.  
  243. int d1 = getDisSquare(x1,y1,x2,y2);
  244. int d2 = getDisSquare(x2,y2,x3,y3);
  245. int d3 = getDisSquare(x3,y3,x1,y1);
  246. if(d1 == d2 && d1 == d3){
  247. return 1;
  248. }
  249. else
  250. return 0;
  251.  
  252. }
  253.  
  254. // checking if , first piont is right angle
  255. bool isRightAngleTriangleHelper(int x1, int y1 ,int x2 , int y2 , int x3 , int y3){
  256.  
  257. int d1 = getDisSquare(x1,y1,x2,y2);
  258. int d2 = getDisSquare(x2,y2,x3,y3);
  259. int d3 = getDisSquare(x3,y3,x1,y1);
  260.  
  261. if(d2 == (d1 + d3)){
  262. return 1;
  263. }
  264. return 0;
  265.  
  266. }
  267.  
  268. bool isRightAngleTriangle(int x1, int y1, int x2 ,int y2 ,int x3 , int y3){
  269.  
  270. if(isRightAngleTriangleHelper(x1,y1,x2,y2,x3,y3) ||
  271. isRightAngleTriangleHelper(x2,y2,x3,y3,x1,y1) ||
  272. isRightAngleTriangleHelper(x3,y3,x1,y1,x2,y2))
  273. return 1;
  274.  
  275. return 0;
  276.  
  277. }
  278.  
  279. bool areCollinear(int x1, int y1,int x2 , int y2 , int x3 , int y3){
  280.  
  281. }
  282.  
  283. // eratoshenes sieve ...
  284. // Once eratoshtenes is activated, use the isPrime function below it,
  285. // and deactivate above function
  286.  
  287. /*
  288.  
  289. int lp[maxn];
  290. vector<int> pr;
  291. void generatePrimes()
  292. {
  293. for (int i=2; i<=maxn; ++i)
  294. {
  295. if (lp[i] == 0)
  296. {
  297. lp[i] = i;
  298. pr.push_back (i);
  299. }
  300. for (unsigned j=0; j<pr.size() && pr[j]<=lp[i] && i*pr[j]<=maxn;)
  301. {
  302. lp[i * pr[j]] = pr[j];
  303. j++;
  304. }
  305. }
  306. return;
  307. }
  308.  
  309. bool isPrime(int n)
  310. {
  311. int root = sqrt(n);
  312. for(int i = 0 ; i < pr.size() && pr[i] <= root ; i++) if(n%pr[i] == 0) return 0;
  313. return 1;
  314. }
  315.  
  316. */
  317.  
  318. /////////////////////////
  319. // declaration section //
  320. /////////////////////////
  321.  
  322. int ncr[1100][1100];
  323. int k ;
  324. string s;
  325.  
  326. void getInput(){
  327.  
  328. cin >> s;
  329. cin >>k;
  330. }
  331.  
  332. void getAnswer(){
  333.  
  334. }
  335.  
  336. vi s1 , s2 , *dp1 , *dp2;
  337.  
  338. int getCount(int index , int remOnes){
  339.  
  340. // cout << " index " << index << " rem ones " << remOnes << endl;
  341. if(remOnes == 0)return 1;
  342.  
  343. if(index == LEN(s)){
  344. return 0;
  345. }
  346.  
  347. int ret = 0;
  348.  
  349. if(s[index] == '1'){
  350.  
  351. int remLen = LEN(s)-index-1;
  352. ret = ncr[remLen][remOnes];
  353. // cout << " before next call of index " << index << " rem ones " << remOnes << " ret " << ret << endl;
  354. ret += getCount(index+1,remOnes-1);
  355. // cout << " leaving index " << index << " rem ones " << remOnes << endl;
  356.  
  357. }
  358. else{
  359. ret = getCount(index+1,remOnes);
  360. }
  361.  
  362. return ret;
  363.  
  364. }
  365.  
  366. bool check(int ones){
  367.  
  368. //cout << " ones " << ones << endl;
  369. //if(ones==0)return false;
  370.  
  371. int counts , reps = 1;
  372.  
  373. while(ones != 1){
  374.  
  375. counts = 0;
  376. while(ones != 0){
  377. if(ones&1)counts++;
  378. ones>>=1;
  379. }
  380. ones = counts;
  381. reps++;
  382.  
  383. }
  384. //cout << " reps " << reps << " k " << k << endl;
  385.  
  386. return(reps >= k);
  387.  
  388. }
  389. void solve(){
  390.  
  391. int ans = 0;
  392.  
  393. if(k==0){
  394. cout << 1 << endl;
  395. return;
  396. }
  397.  
  398. dp1 = &s1 , dp2 = &s2;
  399.  
  400. if(k==1){
  401. cout << LEN(s)-1 << endl;
  402. return;
  403. }
  404.  
  405. repl(i,1,1010){
  406.  
  407. if(check(i) && i <= LEN(s)){
  408.  
  409. //cout << " check sucessful for " << i << endl;
  410. int x = getCount(0,i);
  411. //cout << " adding " << x << endl;
  412. ans = (ans + x)%MOD;
  413. //cout << " ans " << ans << endl;
  414. //NL NL NL
  415.  
  416. }
  417.  
  418. }
  419. //cout << getCount(0,2) << endl;
  420.  
  421. cout << ans << endl;
  422.  
  423. }
  424.  
  425. void pre(){
  426.  
  427. //cout << " pre called " << endl;
  428. rep(i,1050){
  429. ncr[i][0] = 1;
  430. }
  431.  
  432. repl(i,1,1049){
  433. repl(j,1,i){
  434. ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1])%MOD;
  435. }
  436. }
  437.  
  438. // rep(i,10){
  439. // rep(j,i+1){
  440. // cout << ncr[i][j] << " " ;
  441. // }
  442. // NL
  443. // }
  444.  
  445. }
  446.  
  447. signed main(){
  448.  
  449. OPTIMIZE
  450. //check(2) ;
  451. pre();
  452.  
  453. getInput();
  454. solve();
  455. return 0;
  456.  
  457. }
  458.  
Success #stdin #stdout 0s 24696KB
stdin
111111011
2
stdout
498