Problem: As a tradition, every year before IOI all the members of Natalia Fan Club are invited to Malek Dance Club to have a fun night together. Malek Dance Club has 2n members and coincidentally Natalia Fan Club also has 2n members. Each member of MDC is assigned a unique id i from 0 to 2n - 1. The same holds for each member of NFC.

One of the parts of this tradition is one by one dance, where each member of MDC dances with a member of NFC. A dance pair is a pair of numbers (a, b) such that member a from MDC dances with member b from NFC.

The complexity of a pairs' assignment is the number of pairs of dancing pairs (a, b) and (c, d) such that a < c and b > d.

You are given a binary number of length n named x. We know that member i from MDC dances with member <image> from NFC. Your task is to calculate the complexity of this assignment modulo 1000000007 (109 + 7).

Expression <image> denotes applying «XOR» to numbers x and y. This operation exists in all modern programming languages, for example, in C++ and Java it denotes as «^», in Pascal — «xor».

Input

The first line of input contains a binary number x of lenght n, (1 ≤ n ≤ 100).

This number may contain leading zeros.

Output

Print the complexity of the given dance assignent modulo 1000000007 (109 + 7).

Examples

Input

11


Output

6


Input

01


Output

2


Input

1


Output

1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const long double PI = 2 * acos(0.0);
void print(vector<bool> &a) {
  for (bool i : a) {
    cout << i << " ";
  }
  cout << "\n";
}
void print(vector<int> &a) {
  for (int i : a) {
    cout << i << " ";
  }
  cout << "\n";
}
void print(vector<char> &a) {
  for (char i : a) {
    cout << i << " ";
  }
  cout << "\n";
}
void print(vector<long long> &a) {
  for (long long i : a) {
    cout << i << " ";
  }
  cout << "\n";
}
void print(vector<vector<int> > &a) {
  for (vector<int> i : a) {
    print(i);
  }
  cout << "\n";
}
void print(vector<vector<long long> > &a) {
  for (vector<long long> i : a) {
    print(i);
  }
  cout << "\n";
}
void print(vector<double> &a) {
  for (double i : a) {
    cout << i << " ";
  }
  cout << "\n";
}
void print(vector<long double> &a) {
  for (long double i : a) {
    cout << i << " ";
  }
  cout << "\n";
}
void print(vector<pair<long long, long long> > &a) {
  for (pair<long long, long long> i : a) {
    cout << i.first << " " << i.second << "\n";
  }
  cout << "\n";
}
void print(deque<pair<long long, long long> > &a) {
  for (pair<long long, long long> i : a) {
    cout << i.first << " " << i.second << "\n";
  }
  cout << "\n";
}
long long dist_sq(pair<long long, long long> a, pair<long long, long long> b) {
  return ((a.first - b.first) * (a.first - b.first) +
          (a.second - b.second) * (a.second - b.second));
}
long long po(long long a, long long b) {
  if (b <= 0)
    return 1;
  else if (b == 1)
    return a;
  long long vl = po((a * a), b / 2);
  if (b % 2 == 0)
    return vl;
  else
    return (vl)*a;
}
long long pomod(long long a, long long b) {
  a = a % 1000000007LL;
  if (b <= 0)
    return 1 % 1000000007LL;
  else if (b == 1)
    return a % 1000000007LL;
  long long vl = pomod((a * a) % 1000000007LL, b / 2);
  vl = vl % 1000000007LL;
  if (b % 2 == 0)
    return vl;
  else
    return ((vl)*a) % 1000000007LL;
}
long long pomod(long long a, long long b, long long mo) {
  a = a % mo;
  if (b <= 0)
    return 1 % mo;
  else if (b == 1)
    return a % mo;
  long long vl = pomod((a * a) % mo, b / 2);
  vl = vl % mo;
  if (b % 2 == 0)
    return vl;
  else
    return ((vl)*a) % mo;
}
long long factmod(long long n, long long mo) {
  long long val = n;
  long long ans = 1;
  while (val >= 1) {
    ans = (ans * val) % 1000000007LL;
    val--;
  }
  return ans;
}
long long inv(long long a, long long mo) { return pomod(a, mo - 2, mo); }
long long floorlog2(long long n) {
  long long h = 0;
  long long p = 1;
  while (p <= n) {
    h++;
    p *= 2;
  }
  return h - 1;
}
long long floorlog2(long long n, long long b) {
  long long h = 0;
  long long p = 1;
  while (p <= n) {
    h++;
    p *= b;
  }
  return h - 1;
}
struct trie {
  long long occ = 0;
  trie *ch[2];
};
struct trie *new_trie() {
  trie *root = new trie;
  root->occ = 1;
  root->ch[0] = NULL;
  root->ch[1] = NULL;
  return root;
}
long long bit_to_ll(const string &bits) {
  int ln = bits.length();
  long long p = 1;
  long long ans = 0;
  for (long long i = (ln - 1); i >= (0); i--) {
    if (bits[i] == '1') {
      ans += p;
    }
    p *= 2;
  }
  return ans;
}
string ll_to_bit(const long long &el) {
  string ans = "";
  long long tmp = el;
  while (tmp != 0) {
    int d = tmp % 2;
    if (d) {
      ans = "1" + ans;
    } else {
      ans = "0" + ans;
    }
    tmp /= 2;
  }
  int ln = ans.length();
  while (ans.length() != 33) {
    ans = "0" + ans;
  }
  return ans;
}
void insert(trie *root, const long long &el) {
  string str = ll_to_bit(el);
  int len = str.length();
  trie *temp = root;
  for (long long i = (0); i <= (len - 1); i++) {
    char c = str[i];
    if (c == '0') {
      if (temp->ch[0] == NULL) {
        temp->ch[0] = new_trie();
      } else {
        temp->ch[0]->occ++;
      }
      temp = temp->ch[0];
    } else {
      if (temp->ch[1] == NULL) {
        temp->ch[1] = new_trie();
      } else {
        temp->ch[1]->occ++;
      }
      temp = temp->ch[1];
    }
  }
}
void del(trie *root, const long long &el) {
  string str = ll_to_bit(el);
  int len = str.length();
  trie *temp = root;
  for (long long i = (0); i <= (len - 1); i++) {
    char c = str[i];
    if (c == '0') {
      if (temp->ch[0] == NULL) {
        return;
      } else {
        temp->ch[0]->occ--;
      }
      temp = temp->ch[0];
    } else {
      if (temp->ch[1] == NULL) {
        return;
      } else {
        temp->ch[1]->occ--;
      }
      temp = temp->ch[1];
    }
  }
}
long long maxxor(trie *root, const long long &el) {
  string str = ll_to_bit(el);
  int len = str.length();
  trie *temp = root;
  long long mx = el;
  string maxstring = "";
  for (long long i = (0); i <= (len - 1); i++) {
    char c = str[i];
    if (c == '0') {
      if (temp->ch[1] == NULL || temp->ch[1]->occ == 0) {
        maxstring = maxstring + "0";
        temp = temp->ch[0];
      } else {
        maxstring = maxstring + "1";
        temp = temp->ch[1];
      }
    } else {
      if (temp->ch[0] == NULL || temp->ch[0]->occ == 0) {
        maxstring = maxstring + "0";
        temp = temp->ch[1];
      } else {
        maxstring = maxstring + "1";
        temp = temp->ch[0];
      }
    }
  }
  return bit_to_ll(maxstring);
}
void del_trie(trie *root) {
  if (root->ch[1] != NULL) {
    del_trie(root->ch[1]);
  }
  if (root->ch[0] != NULL) {
    del_trie(root->ch[0]);
  }
  delete root;
}
vector<vector<int> > dist(105, vector<int>(105, 0));
vector<vector<bool> > seen(105, vector<bool>(105, 0));
vector<vector<pair<int, int> > > par(105,
                                     vector<pair<int, int> >(105,
                                                             make_pair(0, 0)));
long long compute(string first) {
  int sz = first.size();
  long long ans = 0;
  for (long long i = (sz - 1); i >= (0); i--) {
    ans = (ans * 2) % 1000000007LL;
    if (first[i] == '1') {
      ans = ans + pomod(2, (sz - 1 - i) * 2);
      ans = ans % 1000000007LL;
    }
  }
  return ans;
}
int main(void) {
  ios_base::sync_with_stdio(false);
  string first;
  cin >> first;
  cout << compute(first);
  return 0;
}