#include<bits/stdc++.h> using namespace std; #define int long long string s; const int mod=998244353; int dp[1000005][2][2]; signed main(){ //freopen("pair.in","r",stdin); //freopen("pair.out","w",stdout); cin>>s; int n=s.size(); s=' '+s; dp[0][0][0]=1; for(int i=1;i<s.size();i++){ if(s[i]=='1'){ dp[i][0][1]=dp[i-1][0][0]+dp[i-1][0][1]; dp[i][1][0]=dp[i-1][0][0]+dp[i-1][1][0]; dp[i][1][1]=dp[i-1][0][0]+2*dp[i-1][0][1]+2*dp[i-1][1][0]+3*dp[i-1][1][1]; } else{ dp[i][0][0]=dp[i-1][0][0]; dp[i][0][1]=2*dp[i-1][0][1]; dp[i][1][0]=2*dp[i-1][1][0]; dp[i][1][1]=3*dp[i-1][1][1]; } dp[i][0][0]%=mod; dp[i][0][1]%=mod; dp[i][1][0]%=mod; dp[i][1][1]%=mod; // cout<<dp[i][0][0]<<" "<<dp[i][0][1]<<" "<<dp[i][1][0]<<" "<<dp[i][1][1]<<endl; } cout<<(dp[n][0][0]+dp[n][1][0]+dp[n][0][1]+dp[n][1][1])%mod; // cerr<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; return 0; }