// coding in the memory of Legend :)
//~ mail ID : neernpatel@gmail.com
//~ Author : DrexDelta
//~ codechef : drexdelta , hackerRank : drexdelta , codeforces : drexdelta1
//~ Contact Info : neernpatel@gmail.com
#include<iostream>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define UB upper_bound
#define LB lower_bound
#define ER erase
#define EN end()
#define B begin()
#define I insert
#define OPTIMIZE ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int ll
#define endl "\n"
#define CO cout <<
#define CI cin >>
#define NL cout << endl;
#define DBG {int debug ; cin >> debug;}
#define AND &&
#define OR ||
#define XOR ^
#define OFLUSH fflush(stdout);
#define IFLUSH fflush(stdin);
#define LEN(x) ((int)x.length())
#define rep(i,x) for(int i = 0 ; i < x ; i++)
#define rep1(i,x) for(int i = 1 ; i <= x ; i++)
#define repl(var,start_val,limit_val) for(int var = start_val ; var <= limit_val ; var++)
#define perl(var,start_val,limit_val) for(int var = start_val ; var >= limit_val ; var--)
#define y1 qwert
#define y2 trewq
#define x1 asdfg
#define x2 gfdsa
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef long double ld;
const ll maxn = 2e6+6 ;
const ll MOD = 1e9 + 7;
bool comparator(int i , int j)
{
return (i < j);
}
ll power(ll x, ll i)
{
ll ans = 1;
while(i > 0)
{
if(i&1)
ans = (ans*x)%MOD;
i >>=1;
x = (x*x)%MOD;
}
return ans;
}
ll power(ll x, ll i,ll mod)
{
ll ans = 1;
while(i > 0)
{
if(i&1)
ans = (ans*x)%mod;
i >>=1;
x = (x*x)%mod;
}
return ans;
}
ll modInverse(ll x, ll mod)
{
return power(x , mod-2,mod);
}
bool isPalindrome(string s)
{
int limit = s.length()/2;
for(int i = 0 ; i < limit ; i++)
{
if(s[i] != s[s.length()-i-1])
return 0;
}
return true;
}
ll gcd(ll x, ll y)
{
ll t;
while(y != 0)
{
t = x%y;
x = y;
y = t;
}
return x;
}
bool isVowel(char ch){
if(ch == 'a' || ch == 'i' || ch == 'e' || ch == 'u' || ch == 'o' || ch == 'y'){
return true;
}
return false;
}
bool isPrime(int n)
{
int root = sqrt(n);
for(int i = 2 ; i <= root ; i++) if(n%i == 0) return 0;
return 1;
}
// Geometry
///////////////
ld getDis(ld x1 ,ld y1,ld x2,ld y2){
return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
ld getDisSquare(ld x1,ld y1,ld x2,ld y2){
return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
/////////////
bool isSquareHelper(int x1 , int y1 , int x2 , int y2 , int x3 , int y3 , int x4 , int y4){
ld d1,d2,d3,d4,d5,d6;
d1 = getDisSquare(x1,y1,x2,y2);
d2 = getDisSquare(x2,y2,x3,y3);
d3 = getDisSquare(x3,y3,x4,y4);
d4 = getDisSquare(x4,y4,x1,y1);
if(d1 == d2 && d1 == d3 && d1 == d4){
d5 = getDisSquare(x1,y1,x3,y3);
d6 = getDisSquare(x2,y2,x4,y4);
if(d5 == d6){
return 1;
}
}
return 0;
}
// pass 4 points in any order,
// returns 1 if it forms square, else returns zero
bool isSquare(int x1 ,int y1 , int x2 , int y2 , int x3 , int y3 ,int x4 , int y4){
if( isSquareHelper(x1,y1,x2,y2,x3,y3,x4,y4) ||
isSquareHelper(x1,y1,x2,y2,x4,y4,x3,y3) ||
isSquareHelper(x1,y1,x3,y3,x2,y2,x4,y4) )
return 1;
else
return 0;
}
////////
bool isEqualateralTriangle(int x1, int y1,int x2, int y2, int x3, int y3){
int d1 = getDisSquare(x1,y1,x2,y2);
int d2 = getDisSquare(x2,y2,x3,y3);
int d3 = getDisSquare(x3,y3,x1,y1);
if(d1 == d2 && d1 == d3){
return 1;
}
else
return 0;
}
// checking if , first piont is right angle
bool isRightAngleTriangleHelper(int x1, int y1 ,int x2 , int y2 , int x3 , int y3){
int d1 = getDisSquare(x1,y1,x2,y2);
int d2 = getDisSquare(x2,y2,x3,y3);
int d3 = getDisSquare(x3,y3,x1,y1);
if(d2 == (d1 + d3)){
return 1;
}
return 0;
}
bool isRightAngleTriangle(int x1, int y1, int x2 ,int y2 ,int x3 , int y3){
if(isRightAngleTriangleHelper(x1,y1,x2,y2,x3,y3) ||
isRightAngleTriangleHelper(x2,y2,x3,y3,x1,y1) ||
isRightAngleTriangleHelper(x3,y3,x1,y1,x2,y2))
return 1;
return 0;
}
bool areCollinear(int x1, int y1,int x2 , int y2 , int x3 , int y3){
}
// eratoshenes sieve ...
// Once eratoshtenes is activated, use the isPrime function below it,
// and deactivate above function
/*
int lp[maxn];
vector<int> pr;
void generatePrimes()
{
for (int i=2; i<=maxn; ++i)
{
if (lp[i] == 0)
{
lp[i] = i;
pr.push_back (i);
}
for (unsigned j=0; j<pr.size() && pr[j]<=lp[i] && i*pr[j]<=maxn;)
{
lp[i * pr[j]] = pr[j];
j++;
}
}
return;
}
bool isPrime(int n)
{
int root = sqrt(n);
for(int i = 0 ; i < pr.size() && pr[i] <= root ; i++) if(n%pr[i] == 0) return 0;
return 1;
}
*/
/////////////////////////
// declaration section //
/////////////////////////
int ncr[1100][1100];
int k ;
string s;
void getInput(){
cin >> s;
cin >>k;
}
void getAnswer(){
}
vi s1 , s2 , *dp1 , *dp2;
int getCount(int index , int remOnes){
// cout << " index " << index << " rem ones " << remOnes << endl;
if(remOnes == 0)return 1;
if(index == LEN(s)){
return 0;
}
int ret = 0;
if(s[index] == '1'){
int remLen = LEN(s)-index-1;
ret = ncr[remLen][remOnes];
// cout << " before next call of index " << index << " rem ones " << remOnes << " ret " << ret << endl;
ret += getCount(index+1,remOnes-1);
// cout << " leaving index " << index << " rem ones " << remOnes << endl;
}
else{
ret = getCount(index+1,remOnes);
}
return ret;
}
bool check(int ones){
//cout << " ones " << ones << endl;
//if(ones==0)return false;
int counts , reps = 1;
while(ones != 1){
counts = 0;
while(ones != 0){
if(ones&1)counts++;
ones>>=1;
}
ones = counts;
reps++;
}
//cout << " reps " << reps << " k " << k << endl;
return(reps >= k);
}
void solve(){
int ans = 0;
if(k==0){
cout << 1 << endl;
return;
}
dp1 = &s1 , dp2 = &s2;
if(k==1){
cout << LEN(s)-1 << endl;
return;
}
repl(i,1,1010){
if(check(i) && i <= LEN(s)){
//cout << " check sucessful for " << i << endl;
int x = getCount(0,i);
//cout << " adding " << x << endl;
ans = (ans + x)%MOD;
//cout << " ans " << ans << endl;
//NL NL NL
}
}
//cout << getCount(0,2) << endl;
cout << ans << endl;
}
void pre(){
//cout << " pre called " << endl;
rep(i,1050){
ncr[i][0] = 1;
}
repl(i,1,1049){
repl(j,1,i){
ncr[i][j] = (ncr[i-1][j] + ncr[i-1][j-1])%MOD;
}
}
// rep(i,10){
// rep(j,i+1){
// cout << ncr[i][j] << " " ;
// }
// NL
// }
}
signed main(){
OPTIMIZE
//check(2) ;
pre();
getInput();
solve();
return 0;
}
Ly8gY29kaW5nIGluIHRoZSBtZW1vcnkgb2YgTGVnZW5kIDopIAoKCi8vfiBtYWlsIElEIDogbmVlcm5wYXRlbEBnbWFpbC5jb20KLy9+IEF1dGhvciA6IERyZXhEZWx0YQovL34gY29kZWNoZWYgOiBkcmV4ZGVsdGEgLCBoYWNrZXJSYW5rIDogZHJleGRlbHRhICwgY29kZWZvcmNlcyA6IGRyZXhkZWx0YTEKLy9+IENvbnRhY3QgSW5mbyA6IG5lZXJucGF0ZWxAZ21haWwuY29tCgogCiNpbmNsdWRlPGlvc3RyZWFtPgojaW5jbHVkZSA8Y2N0eXBlPgojaW5jbHVkZSA8Y2Vycm5vPgojaW5jbHVkZSA8Y2Zsb2F0PgojaW5jbHVkZSA8Y2lzbzY0Nj4KI2luY2x1ZGUgPGNsaW1pdHM+CiNpbmNsdWRlIDxjbG9jYWxlPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxjc2V0am1wPgojaW5jbHVkZSA8Y3NpZ25hbD4KI2luY2x1ZGUgPGNzdGRhcmc+CiNpbmNsdWRlIDxjc3RkZGVmPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxjdGltZT4KI2luY2x1ZGUgPGNjb21wbGV4PgojaW5jbHVkZSA8Y2ZlbnY+CiNpbmNsdWRlIDxjaW50dHlwZXM+CiNpbmNsdWRlIDxjc3RkYm9vbD4KI2luY2x1ZGUgPGNzdGRpbnQ+CiNpbmNsdWRlIDxjdGdtYXRoPgojaW5jbHVkZSA8Y3djaGFyPgojaW5jbHVkZSA8Y3djdHlwZT4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGJpdHNldD4KI2luY2x1ZGUgPGNvbXBsZXg+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGV4Y2VwdGlvbj4KI2luY2x1ZGUgPGZzdHJlYW0+CiNpbmNsdWRlIDxmdW5jdGlvbmFsPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPGlvcz4KI2luY2x1ZGUgPGlvc2Z3ZD4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aXN0cmVhbT4KI2luY2x1ZGUgPGl0ZXJhdG9yPgojaW5jbHVkZSA8bGltaXRzPgojaW5jbHVkZSA8bGlzdD4KI2luY2x1ZGUgPGxvY2FsZT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG1lbW9yeT4KI2luY2x1ZGUgPG5ldz4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxvc3RyZWFtPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxzdGRleGNlcHQ+CiNpbmNsdWRlIDxzdHJlYW1idWY+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDx0eXBlaW5mbz4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDx2YWxhcnJheT4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFycmF5PgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KI2luY2x1ZGUgPHVub3JkZXJlZF9zZXQ+CgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgVUIgdXBwZXJfYm91bmQKI2RlZmluZSBMQiBsb3dlcl9ib3VuZAojZGVmaW5lIEVSIGVyYXNlCiNkZWZpbmUgRU4gZW5kKCkKI2RlZmluZSBCIGJlZ2luKCkKI2RlZmluZSBJIGluc2VydAojZGVmaW5lIE9QVElNSVpFIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7Y2luLnRpZSgwKTtjb3V0LnRpZSgwKTsKI2RlZmluZSBpbnQgbGwKI2RlZmluZSBlbmRsICJcbiIKI2RlZmluZSBDTyBjb3V0IDw8CiNkZWZpbmUgQ0kgY2luID4+CiNkZWZpbmUgTkwgY291dCA8PCBlbmRsOwojZGVmaW5lIERCRyB7aW50IGRlYnVnIDsgY2luID4+IGRlYnVnO30KI2RlZmluZSBBTkQgJiYKI2RlZmluZSBPUiB8fAojZGVmaW5lIFhPUiBeCiNkZWZpbmUgT0ZMVVNIIGZmbHVzaChzdGRvdXQpOwojZGVmaW5lIElGTFVTSCBmZmx1c2goc3RkaW4pOwojZGVmaW5lIExFTih4KSAoKGludCl4Lmxlbmd0aCgpKQoKI2RlZmluZSByZXAoaSx4KSBmb3IoaW50IGkgPSAwIDsgaSA8IHggOyBpKyspCiNkZWZpbmUgcmVwMShpLHgpIGZvcihpbnQgaSA9IDEgOyBpIDw9IHggOyBpKyspCgojZGVmaW5lIHJlcGwodmFyLHN0YXJ0X3ZhbCxsaW1pdF92YWwpIGZvcihpbnQgdmFyID0gc3RhcnRfdmFsIDsgdmFyIDw9IGxpbWl0X3ZhbCA7IHZhcisrKQojZGVmaW5lIHBlcmwodmFyLHN0YXJ0X3ZhbCxsaW1pdF92YWwpIGZvcihpbnQgdmFyID0gc3RhcnRfdmFsIDsgdmFyID49IGxpbWl0X3ZhbCA7IHZhci0tKQoKI2RlZmluZSB5MSBxd2VydAojZGVmaW5lIHkyIHRyZXdxCiNkZWZpbmUgeDEgYXNkZmcKI2RlZmluZSB4MiBnZmRzYQoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiBzZXQ8aW50PiBzaTsKdHlwZWRlZiBtdWx0aXNldDxpbnQ+IG1zaTsKdHlwZWRlZiBsb25nIGRvdWJsZSBsZDsKCmNvbnN0IGxsIG1heG4gPSAyZTYrNiA7CmNvbnN0IGxsIE1PRCA9IDFlOSArIDc7Cgpib29sIGNvbXBhcmF0b3IoaW50IGkgLCBpbnQgaikKewogICAgcmV0dXJuIChpIDwgaik7Cn0KCmxsIHBvd2VyKGxsIHgsIGxsIGkpCnsKCWxsIGFucyA9IDE7Cgl3aGlsZShpID4gMCkKCXsKCQlpZihpJjEpCgkJCWFucyA9IChhbnMqeCklTU9EOwoJCWkgPj49MTsKCQl4ID0gKHgqeCklTU9EOwoJfQoJcmV0dXJuIGFuczsKfQoKbGwgcG93ZXIobGwgeCwgbGwgaSxsbCBtb2QpCnsKCWxsIGFucyA9IDE7Cgl3aGlsZShpID4gMCkKCXsKCQlpZihpJjEpCgkJCWFucyA9IChhbnMqeCklbW9kOwoJCWkgPj49MTsKCQl4ID0gKHgqeCklbW9kOwoJfQoJcmV0dXJuIGFuczsKfQoKbGwgbW9kSW52ZXJzZShsbCB4LCBsbCBtb2QpCnsKCXJldHVybiBwb3dlcih4ICwgbW9kLTIsbW9kKTsKfQoKYm9vbCBpc1BhbGluZHJvbWUoc3RyaW5nIHMpCnsKCWludCBsaW1pdCA9IHMubGVuZ3RoKCkvMjsKCWZvcihpbnQgaSA9ICAwIDsgaSA8IGxpbWl0IDsgaSsrKQoJewoJCWlmKHNbaV0gIT0gc1tzLmxlbmd0aCgpLWktMV0pCgkJCXJldHVybiAwOwoJfQoJcmV0dXJuIHRydWU7Cn0KCmxsIGdjZChsbCB4LCBsbCB5KQp7CglsbCB0OwoJd2hpbGUoeSAhPSAwKQoJewoJCXQgPSB4JXk7CgkJeCA9IHk7CgkJeSA9IHQ7Cgl9CglyZXR1cm4geDsKfQoKYm9vbCBpc1Zvd2VsKGNoYXIgY2gpewoKICAgIGlmKGNoID09ICdhJyB8fCBjaCA9PSAnaScgfHwgY2ggPT0gJ2UnIHx8IGNoID09ICd1JyB8fCBjaCA9PSAnbycgfHwgY2ggPT0gJ3knKXsKICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIHJldHVybiBmYWxzZTsKfQoKYm9vbCBpc1ByaW1lKGludCBuKQp7CglpbnQgcm9vdCA9IHNxcnQobik7Cglmb3IoaW50IGkgPSAyIDsgaSA8PSByb290IDsgaSsrKSBpZihuJWkgPT0gMCkgcmV0dXJuIDA7CglyZXR1cm4gMTsKfQoKLy8gR2VvbWV0cnkKLy8vLy8vLy8vLy8vLy8vCgpsZCBnZXREaXMobGQgeDEgLGxkIHkxLGxkIHgyLGxkIHkyKXsKCXJldHVybiBzcXJ0KCh4MS14MikqKHgxLXgyKSArICh5MS15MikqKHkxLXkyKSk7Cn0KCmxkIGdldERpc1NxdWFyZShsZCB4MSxsZCB5MSxsZCB4MixsZCB5Mil7CglyZXR1cm4gKHgxLXgyKSooeDEteDIpICsgKHkxLXkyKSooeTEteTIpOwp9CgovLy8vLy8vLy8vLy8vCmJvb2wgaXNTcXVhcmVIZWxwZXIoaW50IHgxICwgaW50IHkxICwgaW50IHgyICwgaW50IHkyICwgaW50IHgzICwgaW50IHkzICwgaW50IHg0ICwgaW50IHk0KXsKCQoJbGQgZDEsZDIsZDMsZDQsZDUsZDY7CglkMSA9IGdldERpc1NxdWFyZSh4MSx5MSx4Mix5Mik7CglkMiA9IGdldERpc1NxdWFyZSh4Mix5Mix4Myx5Myk7CglkMyA9IGdldERpc1NxdWFyZSh4Myx5Myx4NCx5NCk7CglkNCA9IGdldERpc1NxdWFyZSh4NCx5NCx4MSx5MSk7CgoJaWYoZDEgPT0gZDIgJiYgZDEgPT0gZDMgJiYgZDEgPT0gZDQpewoKCgkJZDUgPSBnZXREaXNTcXVhcmUoeDEseTEseDMseTMpOwoJCWQ2ID0gZ2V0RGlzU3F1YXJlKHgyLHkyLHg0LHk0KTsKCQlpZihkNSA9PSBkNil7CgkJCXJldHVybiAxOwoJCX0KCgl9CglyZXR1cm4gMDsKCn0KCi8vIHBhc3MgNCBwb2ludHMgaW4gYW55IG9yZGVyLCAKLy8gcmV0dXJucyAxIGlmIGl0IGZvcm1zIHNxdWFyZSwgZWxzZSByZXR1cm5zIHplcm8KCmJvb2wgaXNTcXVhcmUoaW50IHgxICxpbnQgeTEgLCBpbnQgeDIgLCBpbnQgeTIgLCBpbnQgeDMgLCBpbnQgeTMgLGludCB4NCAsIGludCB5NCl7CgogICAgaWYoCWlzU3F1YXJlSGVscGVyKHgxLHkxLHgyLHkyLHgzLHkzLHg0LHk0KSB8fCAKICAgIAlpc1NxdWFyZUhlbHBlcih4MSx5MSx4Mix5Mix4NCx5NCx4Myx5MykgfHwgCiAgICAJaXNTcXVhcmVIZWxwZXIoeDEseTEseDMseTMseDIseTIseDQseTQpCSkKICAgIAlyZXR1cm4gMTsKICAgIGVsc2UKICAgIAlyZXR1cm4gMDsKCn0KCi8vLy8vLy8vCmJvb2wgaXNFcXVhbGF0ZXJhbFRyaWFuZ2xlKGludCB4MSwgaW50IHkxLGludCB4MiwgaW50IHkyLCBpbnQgeDMsIGludCB5Myl7CgoJaW50IGQxID0gZ2V0RGlzU3F1YXJlKHgxLHkxLHgyLHkyKTsKCWludCBkMiA9IGdldERpc1NxdWFyZSh4Mix5Mix4Myx5Myk7CglpbnQgZDMgPSBnZXREaXNTcXVhcmUoeDMseTMseDEseTEpOwoJaWYoZDEgPT0gZDIgJiYgZDEgPT0gZDMpewoJCXJldHVybiAxOwoJfQoJZWxzZQoJCXJldHVybiAwOwoKfQoKLy8gY2hlY2tpbmcgaWYgLCBmaXJzdCBwaW9udCBpcyByaWdodCBhbmdsZQpib29sIGlzUmlnaHRBbmdsZVRyaWFuZ2xlSGVscGVyKGludCB4MSwgaW50IHkxICxpbnQgeDIgLCBpbnQgeTIgLCBpbnQgeDMgLCBpbnQgeTMpewoKCWludCBkMSA9IGdldERpc1NxdWFyZSh4MSx5MSx4Mix5Mik7CglpbnQgZDIgPSBnZXREaXNTcXVhcmUoeDIseTIseDMseTMpOwoJaW50IGQzID0gZ2V0RGlzU3F1YXJlKHgzLHkzLHgxLHkxKTsKCglpZihkMiA9PSAoZDEgKyBkMykpewoJCXJldHVybiAxOwoJfQoJcmV0dXJuIDA7Cgp9Cgpib29sIGlzUmlnaHRBbmdsZVRyaWFuZ2xlKGludCB4MSwgaW50IHkxLCBpbnQgeDIgLGludCB5MiAsaW50IHgzICwgaW50IHkzKXsKCglpZihpc1JpZ2h0QW5nbGVUcmlhbmdsZUhlbHBlcih4MSx5MSx4Mix5Mix4Myx5MykgfHwgCgkJaXNSaWdodEFuZ2xlVHJpYW5nbGVIZWxwZXIoeDIseTIseDMseTMseDEseTEpIHx8CgkJICBpc1JpZ2h0QW5nbGVUcmlhbmdsZUhlbHBlcih4Myx5Myx4MSx5MSx4Mix5MikpIAoJCXJldHVybiAxOwoKCXJldHVybiAwOwoJCn0KCmJvb2wgYXJlQ29sbGluZWFyKGludCB4MSwgaW50IHkxLGludCB4MiAsIGludCB5MiAsIGludCB4MyAsIGludCB5Myl7Cgp9CgovLyBlcmF0b3NoZW5lcyBzaWV2ZSAuLi4KLy8gT25jZSBlcmF0b3NodGVuZXMgaXMgYWN0aXZhdGVkLCB1c2UgdGhlIGlzUHJpbWUgZnVuY3Rpb24gYmVsb3cgaXQsCi8vIGFuZCBkZWFjdGl2YXRlIGFib3ZlIGZ1bmN0aW9uCgovKgoKaW50IGxwW21heG5dOwp2ZWN0b3I8aW50PiBwcjsKdm9pZCBnZW5lcmF0ZVByaW1lcygpCnsKCWZvciAoaW50IGk9MjsgaTw9bWF4bjsgKytpKQoJewoJCWlmIChscFtpXSA9PSAwKQoJCXsKCQkJbHBbaV0gPSBpOwoJCQlwci5wdXNoX2JhY2sgKGkpOwoJCX0KCQlmb3IgKHVuc2lnbmVkIGo9MDsgajxwci5zaXplKCkgJiYgcHJbal08PWxwW2ldICYmIGkqcHJbal08PW1heG47KQoJCXsKCQkJbHBbaSAqIHByW2pdXSA9IHByW2pdOwoJCQlqKys7CgkJfQoJfQoJcmV0dXJuOwp9Cgpib29sIGlzUHJpbWUoaW50IG4pCnsKCWludCByb290ID0gc3FydChuKTsKCWZvcihpbnQgaSA9IDAgOyBpIDwgcHIuc2l6ZSgpICYmIHByW2ldIDw9IHJvb3QgOyBpKyspIGlmKG4lcHJbaV0gPT0gMCkgcmV0dXJuIDA7CglyZXR1cm4gMTsKfQoKKi8KCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8KLy8gZGVjbGFyYXRpb24gc2VjdGlvbiAvLwovLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vCgppbnQgbmNyWzExMDBdWzExMDBdOwppbnQgayA7CnN0cmluZyBzOwoKdm9pZCBnZXRJbnB1dCgpewoKCWNpbiA+PiBzOwoJY2luID4+azsKfQoKdm9pZCBnZXRBbnN3ZXIoKXsKCn0KCnZpIHMxICwgczIgLCAqZHAxICwgKmRwMjsKCmludCBnZXRDb3VudChpbnQgaW5kZXggLCBpbnQgcmVtT25lcyl7CgoJLy8gY291dCA8PCAiIGluZGV4ICIgPDwgaW5kZXggPDwgIiByZW0gb25lcyAiIDw8IHJlbU9uZXMgPDwgZW5kbDsKCWlmKHJlbU9uZXMgPT0gMClyZXR1cm4gMTsKCglpZihpbmRleCA9PSBMRU4ocykpewoJCXJldHVybiAwOwoJfQoKCWludCByZXQgPSAwOwoKCWlmKHNbaW5kZXhdID09ICcxJyl7CgoJCWludCByZW1MZW4gPSBMRU4ocyktaW5kZXgtMTsKCQlyZXQgPSBuY3JbcmVtTGVuXVtyZW1PbmVzXTsKCQkvLyBjb3V0IDw8ICIgYmVmb3JlIG5leHQgY2FsbCBvZiBpbmRleCAiIDw8IGluZGV4IDw8ICIgcmVtIG9uZXMgIiA8PCByZW1PbmVzICA8PCAiIHJldCAiIDw8IHJldCA8PCBlbmRsOwoJCXJldCArPSBnZXRDb3VudChpbmRleCsxLHJlbU9uZXMtMSk7CgkJLy8gY291dCA8PCAiIGxlYXZpbmcgaW5kZXggIiA8PCBpbmRleCA8PCAiIHJlbSBvbmVzICIgPDwgcmVtT25lcyA8PCBlbmRsOwoKCX0KCWVsc2V7CgkJcmV0ID0gZ2V0Q291bnQoaW5kZXgrMSxyZW1PbmVzKTsKCX0KCglyZXR1cm4gcmV0OwoKfQoKYm9vbCBjaGVjayhpbnQgb25lcyl7CgoJLy9jb3V0IDw8ICIgb25lcyAiIDw8IG9uZXMgPDwgZW5kbDsKCS8vaWYob25lcz09MClyZXR1cm4gZmFsc2U7CgoJaW50IGNvdW50cyAsIHJlcHMgPSAxOwoKCXdoaWxlKG9uZXMgIT0gMSl7CgoJCWNvdW50cyA9IDA7CgkJd2hpbGUob25lcyAhPSAwKXsKCQkJaWYob25lcyYxKWNvdW50cysrOwoJCQlvbmVzPj49MTsKCQl9CgkJb25lcyA9IGNvdW50czsKCQlyZXBzKys7CgoJfQoJLy9jb3V0IDw8ICIgcmVwcyAiIDw8IHJlcHMgPDwgIiBrICIgPDwgayA8PCBlbmRsOwoKCXJldHVybihyZXBzID49IGspOwoKfQp2b2lkIHNvbHZlKCl7CgoJaW50IGFucyA9IDA7CgoJaWYoaz09MCl7CgkJY291dCA8PCAxIDw8IGVuZGw7CgkJcmV0dXJuOwoJfQoKCWRwMSA9ICZzMSAsIGRwMiA9ICZzMjsKCglpZihrPT0xKXsKCQljb3V0IDw8IExFTihzKS0xIDw8IGVuZGw7CgkJcmV0dXJuOwoJfQoKCXJlcGwoaSwxLDEwMTApewoKCQlpZihjaGVjayhpKSAmJiBpIDw9IExFTihzKSl7CgoJCQkvL2NvdXQgPDwgIiBjaGVjayBzdWNlc3NmdWwgZm9yICIgPDwgaSA8PCBlbmRsOwoJCQlpbnQgeCA9ICBnZXRDb3VudCgwLGkpOwoJCQkvL2NvdXQgPDwgIiBhZGRpbmcgIiA8PCB4IDw8IGVuZGw7CgkJCWFucyA9IChhbnMgKyB4KSVNT0Q7CgkJCS8vY291dCA8PCAiIGFucyAiIDw8IGFucyA8PCBlbmRsOwoJCQkvL05MIE5MIE5MCgoJCX0KCgl9CgkvL2NvdXQgPDwgZ2V0Q291bnQoMCwyKSA8PCBlbmRsOwoKCWNvdXQgPDwgYW5zIDw8IGVuZGw7CiAgICAKfQoKdm9pZCBwcmUoKXsKCgkvL2NvdXQgPDwgIiBwcmUgY2FsbGVkICIgPDwgZW5kbDsKCXJlcChpLDEwNTApewoJCW5jcltpXVswXSA9IDE7Cgl9CgoJcmVwbChpLDEsMTA0OSl7CgkJcmVwbChqLDEsaSl7CgkJCW5jcltpXVtqXSA9IChuY3JbaS0xXVtqXSArIG5jcltpLTFdW2otMV0pJU1PRDsKCQl9Cgl9CgoJLy8gcmVwKGksMTApewoJLy8gCXJlcChqLGkrMSl7CgkvLyAJCWNvdXQgPDwgbmNyW2ldW2pdIDw8ICIgIiA7CgkvLyAJfQoJLy8gCU5MCgkvLyB9Cgp9CgpzaWduZWQgbWFpbigpewoKICAgIE9QVElNSVpFCiAgICAvL2NoZWNrKDIpIDsKICAgIHByZSgpOwoKICAgIGdldElucHV0KCk7CiAgICBzb2x2ZSgpOwogICAgcmV0dXJuIDA7Cgp9Cg==