using ll=long long;using ull=unsigned long long;
#include<limits>
namespace pcl{template<typename T>constexpr T TNF=std::numeric_limits<T>::max()/2;constexpr int INF=TNF<int>;constexpr ll LNF=TNF<ll>;constexpr double DNF=TNF<double>;constexpr double EPS=1e-8;constexpr int P7=1'000'000'007;constexpr int DX[]={1,0,-1,0,1,1,-1,-1};constexpr int DY[]={0,1,0,-1,-1,1,1,-1};}
#include<algorithm>
#include<cmath>
#include<iostream>
namespace pcl{template<typename T>void updmax(T&a,T const&b){a=std::max(a,b);}template<typename T>void updmin(T&a,T const&b){a=std::min(a,b);}template<typename T,typename U,typename V>bool in_range(T const&begin,U const&mid,V const&end){return begin<=mid&&mid<end;}template<typename T,typename U,typename V>bool in_range(T const&begin,std::initializer_list<U>list,V const&end){auto p=std::minmax_element(list.begin(),list.end());return begin<=*p.first&&*p.second<end;}template<typename T,typename U,typename V>bool in_range_strict(T const&begin,std::initializer_list<U>list,V const&end){if(!std::is_sorted(list.begin(),list.end()))return false;return in_range(begin,list,end);}template<typename T>inline T cget(){T x;std::cin>>x;return x;}}
#include<iostream>
#include<vector>
namespace pcl{template<typename T>std::ostream&operator<<(std::ostream&os,std::vector<T>const&v){os<<'[';for(size_t i=0;i<v.size();i++){if(i!=0)os<<",";os<<v[i];}os<<']';return os;}template<typename T>std::istream&operator>>(std::istream&is,std::vector<T>&v){for(size_t i=0;i<v.size();i++)is>>v[i];return is;}}
#include<cmath>
#include<tuple>
#include<utility>
#include<vector>
namespace pcl{template<typename T>constexpr T gcd(T a,T b){return b==0?a:gcd(b,a%b);}template<typename T>constexpr T lcm(T a,T b){return a/gcd(a,b)*b;}template<typename T>constexpr std::tuple<T,T,T>extgcd(T a,T b){if(b==0){return std::make_tuple(a,1,0);}else{T gcd,xd,yd;std::tie(gcd,xd,yd)=extgcd(b,a%b);return std::make_tuple(gcd,yd,xd-(a/b)*yd);}}template<typename T>std::vector<T>sieve(T N){std::vector<T>res;std::vector<bool>is_not_prime(N);for(T i=2;i<=N;i++){if(is_not_prime[i])continue;res.push_back(i);for(T j=i+i;j<=N;j+=i)is_not_prime[j]=true;}return res;}template<typename T>constexpr T pow(T x,int n){T res=1;while(n>0){if(n&1)res*=x;x*=x;n>>=1;}return res;}template<typename T>constexpr bool is_prime(T val){for(T i=2;i<val;i++){if(val%i==0)return false;}return true;}}namespace pcl{template<ll MOD>class modint{private:ll v_;static inline ll inv(ll a){return inv_impl(a,MOD);}static inline ll inv_impl(ll a,ll m){return(a==1?1:(1-m*inv_impl(m%a,a))/a+m);}inline void normalize(){v_%=MOD;if(v_<0)v_+=MOD;}template<ll MOD_>friend bool operator==(modint<MOD_>const&a,modint<MOD_>const&b);template<ll MOD_>friend bool operator!=(modint<MOD_>const&a,modint<MOD_>const&b);template<ll MOD_>friend bool operator<(modint<MOD_>const&a,modint<MOD_>const&b);template<ll MOD_>friend bool operator>(modint<MOD_>const&a,modint<MOD_>const&b);template<ll MOD_>friend bool operator<=(modint<MOD_>const&a,modint<MOD_>const&b);template<ll MOD_>friend bool operator>=(modint<MOD_>const&a,modint<MOD_>const&b);public:modint():v_(0ll){}modint(modint const&init):v_(init.v_){}modint(ll init):v_(init){normalize();}explicit operator ll()const{return v_;}modint&operator+=(modint const&o){v_+=o.v_;normalize();return*this;}modint&operator-=(modint const&o){v_-=o.v_;normalize();return*this;}modint&operator*=(modint const&o){v_*=o.v_;normalize();return*this;}modint&operator/=(modint const&o){ll i=inv(o.v_);*this*=i;return*this;}modint&operator=(modint const&o){v_=o.v_;return*this;}modint&operator+=(ll o){return*this+=modint(o);}modint&operator-=(ll o){return*this-=modint(o);}modint&operator*=(ll o){return*this*=modint(o);}modint&operator/=(ll o){return*this/=modint(o);}modint&operator=(ll o){return*this=modint(o);}modint&operator++(){v_++;if(v_==MOD)v_=0;return*this;}modint&operator--(){if(v_==0)v_=MOD;v_--;return*this;}};template<ll MOD>bool operator==(modint<MOD>const&a,modint<MOD>const&b){return a.v_==b.v_;}template<ll MOD>bool operator!=(modint<MOD>const&a,modint<MOD>const&b){return!(a==b);}template<ll MOD>bool operator<(modint<MOD>const&a,modint<MOD>const&b){return a.v_<b.v_;}template<ll MOD>bool operator>(modint<MOD>const&a,modint<MOD>const&b){return b<a;}template<ll MOD>bool operator<=(modint<MOD>const&a,modint<MOD>const&b){return a<b||a==b;}template<ll MOD>bool operator>=(modint<MOD>const&a,modint<MOD>const&b){return b<=a;}template<ll MOD>bool operator==(modint<MOD>const&a,ll b){return a==modint<MOD>(b);}template<ll MOD>bool operator!=(modint<MOD>const&a,ll b){return a!=modint<MOD>(b);}template<ll MOD>bool operator<(modint<MOD>const&a,ll b){return a<modint<MOD>(b);}template<ll MOD>bool operator>(modint<MOD>const&a,ll b){return a>modint<MOD>(b);}template<ll MOD>bool operator<=(modint<MOD>const&a,ll b){return a<=modint<MOD>(b);}template<ll MOD>bool operator>=(modint<MOD>const&a,ll b){return a>=modint<MOD>(b);}template<ll MOD>bool operator==(ll a,modint<MOD>const&b){return modint<MOD>(a)==b;}template<ll MOD>bool operator!=(ll a,modint<MOD>const&b){return modint<MOD>(a)!=b;}template<ll MOD>bool operator<(ll a,modint<MOD>const&b){return modint<MOD>(a)<b;}template<ll MOD>bool operator>(ll a,modint<MOD>const&b){return modint<MOD>(a)>b;}template<ll MOD>bool operator<=(ll a,modint<MOD>const&b){return modint<MOD>(a)<=b;}template<ll MOD>bool operator>=(ll a,modint<MOD>const&b){return modint<MOD>(a)>=b;}template<ll MOD>modint<MOD>operator+(modint<MOD>a,modint<MOD>const&b){return a+=b;}template<ll MOD>modint<MOD>operator-(modint<MOD>a,modint<MOD>const&b){return a-=b;}template<ll MOD>modint<MOD>operator*(modint<MOD>a,modint<MOD>const&b){return a*=b;}template<ll MOD>modint<MOD>operator/(modint<MOD>a,modint<MOD>const&b){return a/=b;}template<ll MOD>modint<MOD>operator+(modint<MOD>a,ll b){return a+=modint<MOD>(b);}template<ll MOD>modint<MOD>operator-(modint<MOD>a,ll b){return a-=modint<MOD>(b);}template<ll MOD>modint<MOD>operator*(modint<MOD>a,ll b){return a*=modint<MOD>(b);}template<ll MOD>modint<MOD>operator/(modint<MOD>a,ll b){return a/=modint<MOD>(b);}template<ll MOD>modint<MOD>operator+(ll a,modint<MOD>const&b){return modint<MOD>(a)+=b;}template<ll MOD>modint<MOD>operator-(ll a,modint<MOD>const&b){return modint<MOD>(a)-=b;}template<ll MOD>modint<MOD>operator*(ll a,modint<MOD>const&b){return modint<MOD>(a)*=b;}template<ll MOD>modint<MOD>operator/(ll a,modint<MOD>const&b){return modint<MOD>(a)/=b;}template<ll MOD>std::ostream&operator<<(std::ostream&os,modint<MOD>const&x){return os<<static_cast<ll>(x);}template<ll MOD>std::istream&operator>>(std::istream&is,modint<MOD>&x){ll v;is>>v,x=v;return is;}using mint=modint<P7>;}
#include<bits/stdc++.h>
using namespace std;using namespace pcl;int main(){string L;cin>>L;vector<mint>dp1(L.size());vector<mint>dp2(L.size());dp1[0]=1;dp2[0]=2;for(int i=1;i<(int)L.size();i++){switch(L[i]){case '1':dp1[i]=dp1[i-1]*3+dp2[i-1];dp2[i]=dp2[i-1]*2;break;case '0':dp1[i]=dp1[i-1]*3;dp2[i]=dp2[i-1];break;}}cout<<dp1[L.size()-1]+dp2[L.size()-1]<<endl;}


Measured memory_bytes: 2048