Problem: As a tradition, every year before IOI all the members of Natalia Fan Club are invited to Malek Dance Club to have a fun night together. Malek Dance Club has 2n members and coincidentally Natalia Fan Club also has 2n members. Each member of MDC is assigned a unique id i from 0 to 2n - 1. The same holds for each member of NFC.

One of the parts of this tradition is one by one dance, where each member of MDC dances with a member of NFC. A dance pair is a pair of numbers (a, b) such that member a from MDC dances with member b from NFC.

The complexity of a pairs' assignment is the number of pairs of dancing pairs (a, b) and (c, d) such that a < c and b > d.

You are given a binary number of length n named x. We know that member i from MDC dances with member <image> from NFC. Your task is to calculate the complexity of this assignment modulo 1000000007 (109 + 7).

Expression <image> denotes applying «XOR» to numbers x and y. This operation exists in all modern programming languages, for example, in C++ and Java it denotes as «^», in Pascal — «xor».

Input

The first line of input contains a binary number x of lenght n, (1 ≤ n ≤ 100).

This number may contain leading zeros.

Output

Print the complexity of the given dance assignent modulo 1000000007 (109 + 7).

Examples

Input

11


Output

6


Input

01


Output

2


Input

1


Output

1

Solution (in JAVA):

Solution:
//import com.sun.org.apache.xpath.internal.operations.String;

//import com.sun.org.apache.xpath.internal.operations.String;

import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.util.*;


public class scratch_25 {
    // int count=0;
    //static long count=0;
    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        /**
         * call this method to initialize reader for InputStream
         */
        static void init(InputStream input) {
            reader = new BufferedReader(
                    new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        /**
         * get next word
         */
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                //TODO add check for eof if necessary
                tokenizer = new StringTokenizer(
                        reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        static long nextLong() throws IOException {
            return Long.parseLong(next());
        }
    }

    public static class Graph{
        public static class Vertex{
            HashMap<Integer,Integer> nb= new HashMap<>();     // for neighbours of each vertex
        }

        public static HashMap<Integer,Vertex> vt;   // for vertices(all)

        public Graph(){
            vt= new HashMap<>();
        }

        public static int numVer(){
            return vt.size();
        }

        public static boolean contVer(int ver){
            return vt.containsKey(ver);
        }

        public static void addVer(int ver){
            Vertex v= new Vertex();
            vt.put(ver,v);
        }

        public static int numEdg(){
            int count=0;
            ArrayList<Integer> vrtc= new ArrayList<>(vt.keySet());
            for (int i = 0; i <vrtc.size() ; i++) {
                count+=(vt.get(vrtc.get(i))).nb.size();
            }
            return count/2;
        }

        public static boolean contEdg(int ver1, int ver2){
            if(vt.get(ver1)==null || vt.get(ver2)==null){
                return false;
            }

            Vertex v= vt.get(ver1);
            if(v.nb.containsKey(ver2)){
                return true;
            }
            return false;
        }

        public static void addEdge(int ver1, int ver2, int weight){
            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }
            Vertex v1= vt.get(ver1);
            Vertex v2= vt.get(ver2);
            v1.nb.put(ver2,weight);                                 // if previously there is an edge, then this replaces that edge
            v2.nb.put(ver1,weight);
        }

        public static void delEdge(int ver1, int ver2){

            if(!vt.containsKey(ver1) || !vt.containsKey(ver2)){
                return;
            }

            vt.get(ver1).nb.remove(ver2);
            vt.get(ver2).nb.remove(ver1);

        }

        public static void delVer(int ver){
            if(!vt.containsKey(ver)){
                return;
            }
            Vertex v1= vt.get(ver);
            ArrayList<Integer> arr= new ArrayList<>(v1.nb.keySet());
            for (int i = 0; i <arr.size() ; i++) {
                int s= arr.get(i);
                vt.get(s).nb.remove(ver);
            }
            vt.remove(ver);
        }

        public class Pair{
            int vname;
            ArrayList<Integer> psf= new ArrayList<>();       // path so far
            int dis;
            int col;
        }









        public HashMap<Integer,Integer> bfs(int src){
            HashMap<Integer, Boolean> prcd= new HashMap<>();    // jo jo ho chuke hain unke liye

            HashMap<Integer, Integer> ans= new HashMap<>();

            LinkedList<Pair> queue= new LinkedList<>();      // for bfs queue

            Pair strtp= new Pair();

            strtp.vname= src;

            ArrayList<Integer> ar= new ArrayList<>();
            ar.add(src);

            strtp.psf= ar;
            strtp.dis=0;

            queue.addLast(strtp);

            while(!queue.isEmpty()){

                Pair rp =  queue.removeFirst();

                if(prcd.containsKey(rp.vname)){
                    continue;
                }
                prcd.put(rp.vname,true);
                ans.put(rp.vname,rp.dis);

//                if(contEdg(rp.vname,dst)){
//                    return true;
//                }

                Vertex a= vt.get(rp.vname);
                ArrayList<Integer> arr= new ArrayList<>(a.nb.keySet());
                for (int i = 0; i <arr.size() ; i++) {
                    int s= arr.get(i);
                    if(!prcd.containsKey(s)){
                        Pair np = new Pair();
                        np.vname= s;
                        np.dis+=rp.dis+a.nb.get(s);
                        np.psf.addAll(rp.psf);
                        np.psf.add(s);
//                        np.psf.add(s);
//                         np.psf= rp.psf+" "+s;
                        queue.addLast(np);
                    }

                }
            }
            return ans;

            //   return false;
        }








        public HashMap<Integer,Integer> dfs(int src){
            HashMap<Integer, Boolean> prcd= new HashMap<>();    // jo jo ho chuke hain unke liye

            HashMap<Integer, Integer> ans= new HashMap<>();

            LinkedList<Pair> stack= new LinkedList<>();      // for bfs queue

            Pair strtp= new Pair();

            strtp.vname= src;

            ArrayList<Integer> ar= new ArrayList<>();
            ar.add(src);

            strtp.psf= ar;
            strtp.dis=0;

            stack.addFirst(strtp);

            while(!stack.isEmpty()){

                Pair rp =  stack.removeFirst();

                if(prcd.containsKey(rp.vname)){
                    continue;
                }
                prcd.put(rp.vname,true);
                ans.put(rp.vname,rp.dis);

//                if(contEdg(rp.vname,dst)){
//                    return true;
//                }

                Vertex a= vt.get(rp.vname);
                ArrayList<Integer> arr= new ArrayList<>(a.nb.keySet());
                for (int i = 0; i <arr.size() ; i++) {
                    int s= arr.get(i);
                    if(!prcd.containsKey(s)){
                        Pair np = new Pair();
                        np.vname= s;
                        np.dis+=rp.dis+a.nb.get(s);
                        np.psf.addAll(rp.psf);
                        np.psf.add(s);
//                        np.psf.add(s);
//                         np.psf= rp.psf+" "+s;
                        stack.addFirst(np);
                    }

                }
            }
            return ans;

            //   return false;
        }






        public boolean isCycle(){
            HashMap<Integer, Boolean> prcd= new HashMap<>();    // jo jo ho chuke hain unke liye

            //   HashMap<Integer, Integer> ans= new HashMap<>();

            LinkedList<Pair> queue= new LinkedList<>();      // for bfs queue



            ArrayList<Integer> keys = new ArrayList<>(vt.keySet());
            for (int i = 0; i <keys.size(); i++) {
                int cur= keys.get(i);
                if(prcd.containsKey(cur)){
                    continue;
                }

                Pair sp = new Pair();
                sp.vname= cur;
                ArrayList<Integer> as= new ArrayList<>();
                as.add(cur);
                sp.psf= as;

                queue.addLast(sp);

                while(!queue.isEmpty()){




                    Pair rp= queue.removeFirst();
                    if(prcd.containsKey(rp.vname)){
                        return true;
                    }

                    prcd.put(rp.vname,true);




                    Vertex v1= vt.get(rp.vname);
                    ArrayList<Integer> nbrs= new ArrayList<>(v1.nb.keySet());
                    for (int j = 0; j <nbrs.size() ; j++) {
                        int u= nbrs.get(j);
                        Pair np= new Pair();
                        np.vname= u;
                        queue.addLast(np);
                    }
                }

            }
            return false;
        }






        public  ArrayList<ArrayList<Integer>> genConnctdComp(){
            HashMap<Integer, Boolean> prcd= new HashMap<>();    // jo jo ho chuke hain unke liye

            ArrayList<ArrayList<Integer>> ans= new ArrayList<>();

            //   HashMap<Integer, Integer> ans= new HashMap<>();

            LinkedList<Pair> queue= new LinkedList<>();      // for bfs queue

            //  int con=-1;

            ArrayList<Integer> keys = new ArrayList<>(vt.keySet());
            for (int i = 0; i <keys.size(); i++) {
                int cur= keys.get(i);
                if(prcd.containsKey(cur)){
                    //return true;
                    continue;
                }
                int count=0;
                ArrayList<Integer> fu= new ArrayList<>();
                fu.add(cur);


                Pair sp = new Pair();
                sp.vname= cur;
                ArrayList<Integer> as= new ArrayList<>();
                as.add(cur);
                sp.psf= as;

                queue.addLast(sp);

                while(!queue.isEmpty()){




                    Pair rp= queue.removeFirst();
                    if(prcd.containsKey(rp.vname)){
                        //return true;
                        continue;
                    }

                    prcd.put(rp.vname,true);
                    fu.add(rp.vname);



                    Vertex v1= vt.get(rp.vname);
                    ArrayList<Integer> nbrs= new ArrayList<>(v1.nb.keySet());
                    for (int j = 0; j <nbrs.size() ; j++) {
                        int u= nbrs.get(j);
                        if(!prcd.containsKey(u)){
                            count++;
                            Pair np= new Pair();
                            np.vname= u;
                            queue.addLast(np);
                        }
                    }}
                fu.add(count);
                ans.add(fu);

            }
            //return false;
            return ans;

        }

        public boolean isBip(int src){                       // only for connected graph

            HashMap<Integer,Integer> clr= new HashMap<>();
            // colors are 1 and -1


            LinkedList<Integer>q = new LinkedList<Integer>();
            clr.put(src,1);
            q.add(src);


            while(!q.isEmpty()){

                int u = q.getFirst();
                q.pop();

                ArrayList<Integer> arr= new ArrayList<>(vt.keySet());

                for (int i = 0; i <arr.size() ; ++i) {

                    int x= arr.get(i);

                    if(vt.get(u).nb.containsKey(x) && !clr.containsKey(x)){

                        if(clr.get(u)==1){
                            clr.put(x,-1);
                        }
                        else{
                            clr.put(x,1);
                        }
                        q.push(x);
                    }

                    else if(vt.get(u).nb.containsKey(x) && (clr.get(x)==clr.get(u))){
                        return false;
                    }

                }
            }
            return true;
        }

















        public static void printGr() {
            ArrayList<Integer> arr= new ArrayList<>(vt.keySet());
            for (int i = 0; i <arr.size() ; i++) {
                int ver= arr.get(i);
                Vertex v1= vt.get(ver);
                ArrayList<Integer> arr1= new ArrayList<>(v1.nb.keySet());
                for (int j = 0; j <arr1.size() ; j++) {
                    System.out.println(ver+"-"+arr1.get(j)+":"+v1.nb.get(arr1.get(j)));
                }

            }
        }
    }

    static class Cus implements Comparable<Cus>{
        int size;
        int mon;
        int num;
        public Cus(int size,int mon,int num){
            this.size=size;
            this.mon=mon;
            this.num=num;
        }
        @Override
        public int compareTo(Cus o){
            if(this.mon!=o.mon){
                return this.mon-o.mon;}

            else{
                return o.size-this.size;
            }

        }



    }

    static class Table implements Comparable<Table>{
        int go;
      //  int cum;
        int cost;
        public Table(int go,int cost){
            this.go=go;
        //    this.cum=cum;
            this.cost=cost;
        }
        @Override
        public int compareTo(Table o){
           
            return this.cost-o.cost;

        }


    }
    static class Table1 implements Comparable<Table1>{
        int go;
        //int cum;
        int cost;
        public Table1(int go,int cost){
            this.go=go;
          //  this.cum=cum;
            this.cost=cost;
        }
        @Override
        public int compareTo(Table1 o){
            return this.cost-o.cost;


        }}

    public static class DisjointSet{
        HashMap<Integer,Node> mp= new HashMap<>();

        public static class Node{
            int data;
            Node parent;
            int rank;
        }


        public void create(int val){
            Node nn= new Node();
            nn.data=val;
            nn.parent=nn;
            nn.rank=0;
            mp.put(val,nn);
        }

        public int find(int val){

            return findn(mp.get(val)).data;

        }


        public Node findn(Node n){
            if(n==n.parent){
                return n;
            }
            Node rr= findn(n.parent);
            n.parent=rr;
            return rr;
        }



        public void union(int val1, int val2){                                                                               // can also be used to check cycles

            Node n1= findn(mp.get(val1));
            Node n2= findn(mp.get(val2));


            if(n1.data==n2.data) {
                return;
            }



            if(n1.rank<n2.rank){
                n1.parent=n2;
            }

            else if(n2.rank<n1.rank){
                n2.parent=n1;
            }

            else {
                n2.parent=n1;
                n1.rank++;
            }

        }
    }









    public static void main(String[] args)  throws IOException {
        Reader.init(System.in);
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        String s= Reader.next();
        int n= s.length();
        long mod=1000000000+7;
        long ans=0;
        if(s.charAt(n-1)=='1'){
        ans=1;
        }

        for (int i = n-2; i >=0 ; i--) {
            if((s.charAt(i))=='0'){
                ans=(2*ans)%mod;
            }
            else if(s.charAt(i)=='1'){
                ans=((2*ans)%mod + power(2,2*((n-i)-1),mod))%mod;
            }

        }

        System.out.println(ans);




    }
    static long power( long x, long y, long p)
    {
        // Initialize result
        long res = 1;

        // Update x if it is more
        // than or equal to p
        x = x % p;

        if (x == 0) return 0; // In case x is divisible by p;

        while (y > 0)
        {
            // If y is odd, multiply x
            // with result
            if((y & 1)==1)
                res = (res * x) % p;

            // y must be even now
            // y = y / 2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static long ceil_div(long a, long b){
        return (a+b-1)/b;
    }

    static int countDivisibles(int A, int B, int M)
    {
        // Add 1 explicitly as A is divisible by M
        if (A % M == 0)
            return (B / M) - (A / M) + 1;

        // A is not divisible by M
        return (B / M) - (A / M);
    }


    public static void df(int x, int y,int n, int m, char[][]ar, int l){
        boolean done[][]= new boolean[n][m];
        int count=0;
        LinkedList<int[]> stk= new LinkedList<>();
        int a[]= {x,y};
        stk.addFirst(a);
        while(!stk.isEmpty() && count<l){
            //  count++;
            int b[]=stk.removeFirst();
            if( done[b[0]][b[1]]){
                continue;
            }
            count++;

            done[b[0]][b[1]]=true;
            ar[b[0]][b[1]]='@';
            int arr[][]={{1,0},{-1,0},{0,1},{0,-1}};
            for (int i = 0; i <arr.length ; i++) {
                if(!(b[0]+arr[i][0]>=n || b[1]+arr[i][1]>=m || b[0]+arr[i][0]<0 || b[1]+arr[i][1]<0 ||  ar[b[0]+arr[i][0]][b[1]+arr[i][1]]=='#')){
                    int r[]= {b[0]+arr[i][0], b[1]+arr[i][1]};
                    stk.addFirst(r);
                    // continue;



                }
            }}


        for (int i = 0; i <n ; i++) {
            for (int j = 0; j <m ; j++) {
                if(ar[i][j]=='.'){
                    System.out.print('X');
                }
                else if(ar[i][j]=='@'){
                    System.out.print('.');
                }
                else{
                    System.out.print(ar[i][j]);
                }
            }
            System.out.println();
        }
























    }











    static long gcd(long a, long b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }



    static long gcd1(long a, long b)
    {

        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // base case
        if (a == b)
            return a;

        // a is greater
        //count++;
        if (a > b){
            return gcd(a-b, b);

        }
        return gcd(a, b-a);
    }





    // method to return LCM of two numbers
    static long lcm(long a, long b)
    {
        return (a*b)/gcd(a, b);
    }

    // Driver method

    static int partition(long arr[],long arr1[], int low, int high)
    {
        long pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than the pivot
            if (arr[j] < pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                long temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                long temp1=arr1[i];
                arr1[i]=arr1[j];
                arr1[j]=temp1;

            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        long temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;
        long temp1= arr1[i+1];
        arr1[i+1]=arr1[high];
        arr1[high]= temp1;

        return i+1;
    }


    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */
    static void sort(long arr[],long arr1[], int low, int high)
    {
        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr,arr1, low, high);

            // Recursively sort elements before
            // partition and after partition
            sort(arr,arr1, low, pi-1);
            sort(arr,arr1, pi+1, high);
        }
    }







































































    public static ArrayList<Integer> Sieve(int n) {
        boolean arr[]= new boolean [n+1];
        Arrays.fill(arr,true);
        arr[0]=false;
        arr[1]=false;
        for (int i = 2; i*i <=n ; i++) {
            if(arr[i]){
                for (int j = 2; j <=n/i ; j++) {
                    int u= i*j;
                    arr[u]=false;
                }}
        }
        ArrayList<Integer> ans= new ArrayList<>();
        for (int i = 0; i <n+1 ; i++) {
            if(arr[i]){
                ans.add(i);
            }
        }
        return ans;










    }





}