Problem: The gym leaders were fascinated by the evolutions which took place at Felicity camp. So, they were curious to know about the secret behind evolving Pokemon. 

The organizers of the camp gave the gym leaders a PokeBlock, a sequence of n ingredients. Each ingredient can be of type 0 or 1. Now the organizers told the gym leaders that to evolve a Pokemon of type k (k ≥ 2), they need to make a valid set of k cuts on the PokeBlock to get smaller blocks.

Suppose the given PokeBlock sequence is b0b1b2... bn - 1. You have a choice of making cuts at n + 1 places, i.e., Before b0, between b0 and b1, between b1 and b2, ..., between bn - 2 and bn - 1, and after bn - 1.

The n + 1 choices of making cuts are as follows (where a | denotes a possible cut):

| b0 | b1 | b2 | ... | bn - 2 | bn - 1 |

Consider a sequence of k cuts. Now each pair of consecutive cuts will contain a binary string between them, formed from the ingredient types. The ingredients before the first cut and after the last cut are wasted, which is to say they are not considered. So there will be exactly k - 1 such binary substrings. Every substring can be read as a binary number. Let m be the maximum number out of the obtained numbers. If all the obtained numbers are positive and the set of the obtained numbers contains all integers from 1 to m, then this set of cuts is said to be a valid set of cuts.

For example, suppose the given PokeBlock sequence is 101101001110 and we made 5 cuts in the following way:

10 | 11 | 010 | 01 | 1 | 10

So the 4 binary substrings obtained are: 11, 010, 01 and 1, which correspond to the numbers 3, 2, 1 and 1 respectively. Here m = 3, as it is the maximum value among the obtained numbers. And all the obtained numbers are positive and we have obtained all integers from 1 to m. Hence this set of cuts is a valid set of 5 cuts.

A Pokemon of type k will evolve only if the PokeBlock is cut using a valid set of k cuts. There can be many valid sets of the same size. Two valid sets of k cuts are considered different if there is a cut in one set which is not there in the other set.

Let f(k) denote the number of valid sets of k cuts. Find the value of <image>. Since the value of s can be very large, output s modulo 109 + 7.

Input

The input consists of two lines. The first line consists an integer n (1 ≤ n ≤ 75) — the length of the PokeBlock. The next line contains the PokeBlock, a binary string of length n.

Output

Output a single integer, containing the answer to the problem, i.e., the value of s modulo 109 + 7.

Examples

Input

4
1011


Output

10


Input

2
10


Output

1

Note

In the first sample, the sets of valid cuts are:

Size 2: |1|011, 1|01|1, 10|1|1, 101|1|.

Size 3: |1|01|1, |10|1|1, 10|1|1|, 1|01|1|.

Size 4: |10|1|1|, |1|01|1|.

Hence, f(2) = 4, f(3) = 4 and f(4) = 2. So, the value of s = 10.

In the second sample, the set of valid cuts is:

Size 2: |1|0.

Hence, f(2) = 1 and f(3) = 0. So, the value of s = 1.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
template <typename T, size_t N>
struct MakeVector {
  template <typename... Args,
            typename R = std::vector<decltype(MakeVector<T, N - 1>::make_vector(
                std::declval<Args>()...))>>
  static R make_vector(std::size_t first, Args... sizes) {
    auto inner = MakeVector<T, N - 1>::make_vector(sizes...);
    return R(first, inner);
  }
};
template <typename T>
struct MakeVector<T, 1> {
  template <typename R = std::vector<T>>
  static R make_vector(std::size_t size, const T& value) {
    return R(size, value);
  }
};
template <typename T, typename... Args>
auto make_vector(Args... args)
    -> decltype(MakeVector<T, sizeof...(Args) - 1>::make_vector(args...)) {
  return MakeVector<T, sizeof...(Args) - 1>::make_vector(args...);
}
template <typename T, typename = std::true_type>
struct IdentityHelper;
template <typename T>
struct IdentityHelper<T, typename std::is_arithmetic<T>::type> {
  static T identity() { return 1; }
};
template <typename T>
T identity() {
  return IdentityHelper<T>::identity();
}
template <typename T>
T extendedGcd(T a, T b, T& x, T& y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  T d = extendedGcd(b % a, a, y, x);
  x -= (b / a) * y;
  return d;
}
template <typename T>
class Zn {
 public:
  Zn() : value(0) {}
  static Zn valueOf(int value) {
    int x = value % mod();
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn valueOf(long long value) {
    int x = static_cast<int>(value % mod());
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  static Zn rawValueOf(int value) {
    ;
    return Zn(value);
  }
  Zn& operator=(int rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator=(long long rhs) { return *this = Zn::valueOf(rhs); }
  Zn& operator+=(const Zn& rhs) {
    value += rhs.value;
    if (value >= mod()) {
      value -= mod();
    }
    return *this;
  }
  Zn& operator+=(int rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator+=(long long rhs) { return *this += Zn::valueOf(rhs); }
  Zn& operator-=(const Zn& rhs) {
    value -= rhs.value;
    if (value < 0) {
      value += mod();
    }
    return *this;
  }
  Zn& operator-=(int rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator-=(long long rhs) { return *this -= Zn::valueOf(rhs); }
  Zn& operator*=(const Zn& rhs) {
    long long result =
        static_cast<long long>(value) * static_cast<long long>(rhs.value);
    value = static_cast<int>(result % mod());
    return *this;
  }
  Zn& operator*=(int rhs) { return *this *= Zn::valueOf(rhs); }
  Zn& operator*=(long long rhs) { return *this *= Zn::valueOf(rhs); }
  Zn operator-() const {
    if (value == 0) {
      return *this;
    } else {
      return Zn(mod() - value);
    }
  }
  Zn& operator/=(const Zn& rhs) { return *this *= rhs.inversed(); }
  Zn& operator/=(int rhs) { return *this /= Zn::valueOf(rhs); }
  Zn& operator/=(long long rhs) { return *this /= Zn::valueOf(rhs); }
  bool operator==(const Zn& rhs) const { return value == rhs.value; }
  Zn inversed() const {
    ;
    int x, y;
    int gcd = extendedGcd(value, mod(), x, y);
    (void)gcd;
    ;
    if (x < 0) {
      x += mod();
    }
    return Zn(x);
  }
  template <typename U>
  friend std::ostream& operator<<(std::ostream&, const Zn<U>& zn);
  template <typename U>
  friend std::istream& operator>>(std::istream&, Zn<U>& zn);
  int intValue() const { return value; }

 private:
  explicit Zn(int value) : value(value) {}
  int value;
  constexpr static int mod() { return T::value; }
  template <int N = T::value>
  static constexpr bool positive_or_runtime(int) {
    return N > 0;
  }
  static constexpr bool positive_or_runtime(...) { return true; }
  static_assert(
      std::is_same<typename std::decay<decltype(T::value)>::type, int>::value,
      "T::value must be int");
  static_assert(positive_or_runtime(0), "Mod has to be positive integer");
};
template <typename T>
bool operator==(const Zn<T>& lhs, int rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(int lhs, const Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator==(const Zn<T>& lhs, long long rhs) {
  return lhs == Zn<T>::valueOf(rhs);
}
template <typename T>
bool operator==(long long lhs, Zn<T>& rhs) {
  return rhs == lhs;
}
template <typename T>
bool operator!=(const Zn<T>& lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, int rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(int lhs, const Zn<T>& rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(const Zn<T>& lhs, long long rhs) {
  return !(lhs == rhs);
}
template <typename T>
bool operator!=(long long rhs, const Zn<T>& lhs) {
  return !(lhs == rhs);
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T>
Zn<T> operator+(int lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator+(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy += rhs;
}
template <typename T>
Zn<T> operator+(long long lhs, const Zn<T>& rhs) {
  return rhs + lhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T>
Zn<T> operator-(int lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator-(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy -= rhs;
}
template <typename T>
Zn<T> operator-(long lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) - rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T>
Zn<T> operator*(int lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator*(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy *= rhs;
}
template <typename T>
Zn<T> operator*(long long lhs, const Zn<T>& rhs) {
  return rhs * lhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, const Zn<T>& rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, int rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T>
Zn<T> operator/(int lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
Zn<T> operator/(const Zn<T>& lhs, long long rhs) {
  Zn<T> copy = lhs;
  return copy /= rhs;
}
template <typename T>
Zn<T> operator/(long long lhs, const Zn<T>& rhs) {
  return Zn<T>::valueOf(lhs) / rhs;
}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const Zn<T>& zn) {
  return stream << zn.value;
}
template <typename T>
std::istream& operator>>(std::istream& stream, Zn<T>& zn) {
  long long value;
  stream >> value;
  zn.value = static_cast<int>(value % T::value);
  return stream;
}
template <typename T>
struct IdentityHelper<Zn<T>> {
  static Zn<T> identity() { return Zn<T>::valueOf(1); }
};
template <int m>
using ZnConst = Zn<std::integral_constant<int, m>>;
template <typename T>
class IntegerIterator
    : public std::iterator<std::input_iterator_tag, T, std::ptrdiff_t, T*, T> {
 public:
  explicit IntegerIterator(T value) : value(value) {}
  IntegerIterator& operator++() {
    ++value;
    return *this;
  }
  IntegerIterator operator++(int) {
    IntegerIterator copy = *this;
    ++value;
    return copy;
  }
  IntegerIterator& operator--() {
    --value;
    return *this;
  }
  IntegerIterator operator--(int) {
    IntegerIterator copy = *this;
    --value;
    return copy;
  }
  T operator*() const { return value; }
  bool operator==(IntegerIterator rhs) const { return value == rhs.value; }
  bool operator!=(IntegerIterator rhs) const { return !(*this == rhs); }

 private:
  T value;
};
template <typename T>
class IntegerRange {
 public:
  IntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  IntegerIterator<T> begin() const { return IntegerIterator<T>(begin_); }
  IntegerIterator<T> end() const { return IntegerIterator<T>(end_); }

 private:
  T begin_;
  T end_;
};
template <typename T>
class ReversedIntegerRange {
 public:
  ReversedIntegerRange(T begin, T end) : begin_(begin), end_(end) { ; }
  std::reverse_iterator<IntegerIterator<T>> begin() const {
    return std::reverse_iterator<IntegerIterator<T>>(
        IntegerIterator<T>(begin_));
  }
  std::reverse_iterator<IntegerIterator<T>> end() const {
    return std::reverse_iterator<IntegerIterator<T>>(IntegerIterator<T>(end_));
  }

 private:
  T begin_;
  T end_;
};
template <typename T>
IntegerRange<T> range(T to) {
  return IntegerRange<T>(0, to);
}
template <typename T>
IntegerRange<T> range(T from, T to) {
  return IntegerRange<T>(from, to);
}
template <typename T>
IntegerRange<T> inclusiveRange(T to) {
  return IntegerRange<T>(0, to + 1);
}
template <typename T>
IntegerRange<T> inclusiveRange(T from, T to) {
  return IntegerRange<T>(from, to + 1);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from) {
  return ReversedIntegerRange<T>(from, 0);
}
template <typename T>
ReversedIntegerRange<T> downrange(T from, T to) {
  return ReversedIntegerRange<T>(from, to);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from) {
  return ReversedIntegerRange<T>(from + 1, 0);
}
template <typename T>
ReversedIntegerRange<T> inclusiveDownrange(T from, T to) {
  return ReversedIntegerRange<T>(from + 1, to);
}
using namespace std;
class TaskD {
 public:
  void solve(std::istream& in, std::ostream& out) {
    int n;
    in >> n;
    string s;
    in >> s;
    auto z = prep(s);
    s = z.first;
    n = s.size();
    vector<int> v(s.size());
    for (auto i : range(s.size())) {
      v[i] = s[i] - '0';
    }
    using Z = ZnConst<1000000007>;
    auto dp = make_vector<Z>(16, 1 << 21, Z());
    vector<int> interesting;
    for (int i : inclusiveRange(1, 21)) {
      interesting.push_back((1 << i) - 1);
    }
    Z ans;
    for (int i : inclusiveRange(n)) {
      if (i != n) dp[i % 16][0] = z.second[i];
      for (auto x : interesting) {
        ans += dp[i % 16][x];
      }
      for (int from : range(1 << 21)) {
        Z res = dp[i % 16][from];
        if (res == Z()) {
          continue;
        }
        int num = 0;
        for (int j = i + 1; j <= n; ++j) {
          assert(j <= n);
          assert(j - i <= 15);
          num = 2 * num + v[j - 1];
          if (num == 0) {
            continue;
          }
          assert(num != 0);
          if (num > 21) {
            break;
          }
          int mask = from | (1 << (num - 1));
          dp[j % 16][mask] += res;
        }
      }
      dp[i % 16].assign(1 << 21, Z());
    }
    out << ans << '\n';
  }
  pair<string, vector<int>> prep(string r) {
    string s;
    vector<int> v;
    int cur = 0;
    for (char c : r) {
      s.push_back(c);
      v.push_back(cur + 1);
      cur = 0;
      if (s.size() >= 8 && s.substr(s.size() - 8) == string(8, '0')) {
        s = s.substr(0, s.size() - 1);
        cur = v.back();
        v.pop_back();
      }
    }
    return make_pair(s, v);
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  TaskD solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  in.tie(0);
  out << std::fixed;
  out.precision(20);
  solver.solve(in, out);
  return 0;
}