Codeforces Round #189 Div2A Magic Numbers

問題

10^9までの数字が与えられるので、それがマジックナンバーかどうかを判定してください。
マジックナンバーは、"1","14","144"の連結で与えられる数字で、
14144, 141414, 1411とかはそうで、1444, 514, 414とかはそうではないです。

解法
・先頭の数が１であること
・4が3個以上連続していないこと
・１，４以外の数字が出てこないこと
が条件となります。
文字列中の144を全部消して、次に14を消して、（ex: "14144" -> "14" -> ""）・・・というやりかたで空文字が得られるか、という判定をしているコードもいくつかありましたが、111444のような例で誤答を出してしまいます。

プログラム

#include<iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include<string>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<sstream>
#include<algorithm>
#include<map>
#include<complex>
using namespace std;


#define li			long long int
#define rep(i,to)	for(int i=0;i<((int)(to));i++)
#define repp(i,start,to)	for(int i=(int)(start);i<((int)(to));i++)
#define pb			push_back
#define sz(v)		((li)(v).size())


int main(){
	string x;
	cin>>x;
	li n=sz(x);
	li res=0;
	li two=1;
	
	rep(i,n){
		if(x[n-i-1]=='0')res=(res*2)%MOD;
		else{
			res=(res*2+two*two)%MOD;
		}
		two=(two*2)%MOD;
	}
	
	cout<<res%MOD<<endl;
	
	return 0;
}