Tes.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <utility>
#include <bitset>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)
#define all(a) (a).begin(), (a).end()

using ll = long long;
constexpr ll mod = 1000000007;
using P = std::pair<std::string, std::string>;

std::string L;
std::map<P, ll> memo;

ll rec( const std::string &lb, const std::string &xb )
{
  if( memo.count(P(lb,xb)) )
    return memo[P(lb,xb)];

  std::cout << "(" << lb << "," << xb << ")" << std::endl;

  if( lb.size() == 1 )
    return lb == "1" && xb == "1" ? 2 : lb == "0" && xb == "0" ? 1 : 0;

  ll ret1 = rec( lb.substr(0,lb.size()-1), xb.substr(0,xb.size()-1) );
  
  std::string x = xb;
  if( xb[xb.size()-1] == '1' )
    l = xb.substr(0,xb.size()-1);
  else
  {
    int p = xb.size()-2;

    while( xb[p] != '1' )
      x[p] = '1', --p;

    x[p] = '0';
    x = x.substr( 0, x.size()-1 );
  }

  ll ret2 = rec( lb.substr(0,lb.size()-1), x );

  return memo[P(lb,xb)] = (ret1+ret2*2%mod)%mod;
}

int main()
{
  std::cin >> L;

  std::cout << rec( L, L ) << std::endl;

  return 0;
}