use crate::mod_int::{set_mod_int, ModInt};
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
set_mod_int(1_000_000_007);
let l = sc
.read::<String>()
.chars()
.map(|c| c as usize - '0' as usize)
.collect::<Vec<_>>();
let n = l.len();
let mut dp = vec![ModInt::new(0); 2];
dp[0] = ModInt::new(1);
for i in 0..n {
let mut next = vec![ModInt::new(0); 2];
let l = l[i];
for a in 0..2 {
for b in 0..2 {
if a == 1 && b == 1 {
continue;
}
let sum = a + b;
for lower in 0..2 {
if lower == 0 && sum > l {
continue;
}
let next_lower = if lower == 1 || sum < l { 1 } else { 0 };
next[next_lower] += dp[lower];
}
}
}
dp = next;
}
let ans = dp[0] + dp[1];
println!("{}", ans.value());
}
pub mod mod_int {
use std::cell::RefCell;
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign};
type InternalNum = i64;
thread_local!(
static MOD: RefCell<InternalNum> = RefCell::new(0);
);
pub fn set_mod_int<T>(v: T)
where
InternalNum: From<T>,
{
MOD.with(|x| x.replace(InternalNum::from(v)));
}
fn modulo() -> InternalNum {
MOD.with(|x| *x.borrow())
}
#[derive(Debug)]
pub struct ModInt(InternalNum);
impl Clone for ModInt {
fn clone(&self) -> Self {
Self(self.0)
}
}
impl Copy for ModInt {}
impl ModInt {
pub fn new<T>(v: T) -> Self
where
InternalNum: From<T>,
{
let mut v = InternalNum::from(v);
let m = modulo();
if v >= m {
v %= m;
}
Self(v)
}
pub fn internal_pow(&self, mut e: InternalNum) -> Self {
let mut result = 1;
let mut cur = self.0;
let modulo = modulo();
while e > 0 {
if e & 1 == 1 {
result *= cur;
result %= modulo;
}
e >>= 1;
cur = (cur * cur) % modulo;
}
Self(result)
}
pub fn pow<T>(&self, e: T) -> Self
where
InternalNum: From<T>,
{
self.internal_pow(InternalNum::from(e))
}
pub fn value(&self) -> InternalNum {
self.0
}
}
impl From<ModInt> for InternalNum {
fn from(m: ModInt) -> Self {
m.value()
}
}
impl<T> AddAssign<T> for ModInt
where
InternalNum: From<T>,
{
fn add_assign(&mut self, rhs: T) {
let mut rhs = InternalNum::from(rhs);
let m = modulo();
if rhs >= m {
rhs %= m;
}
self.0 += rhs;
if self.0 >= m {
self.0 -= m;
}
}
}
impl<T> Add<T> for ModInt
where
InternalNum: From<T>,
{
type Output = ModInt;
fn add(self, rhs: T) -> Self::Output {
let mut res = self;
res += rhs;
res
}
}
impl<T> SubAssign<T> for ModInt
where
InternalNum: From<T>,
{
fn sub_assign(&mut self, rhs: T) {
let mut rhs = InternalNum::from(rhs);
let m = modulo();
if rhs >= m {
rhs %= m;
}
if rhs > 0 {
self.0 += m - rhs;
}
if self.0 >= m {
self.0 -= m;
}
}
}
impl<T> Sub<T> for ModInt
where
InternalNum: From<T>,
{
type Output = Self;
fn sub(self, rhs: T) -> Self::Output {
let mut res = self;
res -= rhs;
res
}
}
impl<T> MulAssign<T> for ModInt
where
InternalNum: From<T>,
{
fn mul_assign(&mut self, rhs: T) {
let mut rhs = InternalNum::from(rhs);
let m = modulo();
if rhs >= m {
rhs %= m;
}
self.0 *= rhs;
self.0 %= m;
}
}
impl<T> Mul<T> for ModInt
where
InternalNum: From<T>,
{
type Output = Self;
fn mul(self, rhs: T) -> Self::Output {
let mut res = self;
res *= rhs;
res
}
}
impl<T> DivAssign<T> for ModInt
where
InternalNum: From<T>,
{
fn div_assign(&mut self, rhs: T) {
let mut rhs = InternalNum::from(rhs);
let m = modulo();
if rhs >= m {
rhs %= m;
}
let inv = Self(rhs).internal_pow(m - 2);
self.0 *= inv.value();
self.0 %= m;
}
}
impl<T> Div<T> for ModInt
where
InternalNum: From<T>,
{
type Output = Self;
fn div(self, rhs: T) -> Self::Output {
let mut res = self;
res /= rhs;
res
}
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> Self {
Self(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
}