Problem: Dreamoon saw a large integer x written on the ground and wants to print its binary form out. Dreamoon has accomplished the part of turning x into its binary format. Now he is going to print it in the following manner.

He has an integer n = 0 and can only perform the following two operations in any order for unlimited times each:

  1. Print n in binary form without leading zeros, each print will append to the right of previous prints. 
  2. Increase n by 1. 



Let's define an ideal sequence as a sequence of operations that can successfully print binary representation of x without leading zeros and ends with a print operation (i.e. operation 1). Dreamoon wants to know how many different ideal sequences are there and the length (in operations) of the shortest ideal sequence.

The answers might be large so please print them modulo 1000000007 (109 + 7).

Let's define the string representation of an ideal sequence as a string of '1' and '2' where the i-th character in the string matches the i-th operation performed. Two ideal sequences are called different if their string representations are different.

Input

The single line of the input contains a binary integer representing x (1 ≤ x < 25000) without leading zeros.

Output

The first line of the output should contain an integer representing the number of different ideal sequences modulo 1000000007 (109 + 7).

The second line of the output contains an integer representing the minimal length of an ideal sequence modulo 1000000007 (109 + 7).

Examples

Input

101


Output

1
6


Input

11010


Output

3
5

Note

For the first sample, the shortest and the only ideal sequence is «222221» of length 6.

For the second sample, there are three ideal sequences «21211», «212222222221», «222222222222222222222222221». Among them the shortest one has length 5.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.io.OutputStreamWriter;
import java.io.OutputStream;
import java.io.IOException;
import java.io.Serializable;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) throws Exception {
        Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 29);
        thread.start();
        thread.join();
    }

    static class TaskAdapter implements Runnable {
        @Override
        public void run() {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            FastInput in = new FastInput(inputStream);
            FastOutput out = new FastOutput(outputStream);
            DDreamoonAndBinary solver = new DDreamoonAndBinary();
            solver.solve(1, in, out);
            out.close();
        }
    }

    static class DDreamoonAndBinary {
        int mod = (int) 1e9 + 7;
        BitSet repr;
        BitSet a;
        BitSet b;
        boolean[] init;
        int[][] next;

        public int compare(int l, int r, int L, int R) {
            assert r - l == R - L;
            int delta = L - l;
            int diffIndex = next[delta][l];
            if (diffIndex > r) {
                return 0;
            }
            return init[diffIndex] ? 1 : -1;
        }

        private long valueOf(char[] s, int a) {
            return Long.valueOf(String.valueOf(s, a, s.length - a), 2);
        }

        public int compare(char[] s, int a, int k1, int b, int k2) {
            if (s.length - a >= 32 || s.length - b >= 32) {
                return -Integer.compare(a, b);
            }
            return Long.compare(valueOf(s, a) + k1, valueOf(s, b) + k2);
        }

        public void solve(int testNumber, FastInput in, FastOutput out) {
            char[] s = in.rs().toCharArray();
            int n = s.length;
            repr = new BitSet(n);
            a = new BitSet(n);
            b = new BitSet(n);
            init = new boolean[n];
            next = new int[n][n];
            boolean[] xor = new boolean[n];
            for (int i = 0; i < n; i++) {
                init[i] = s[i] == '1';
            }
            for (int i = 1; i < n; i++) {
                Arrays.fill(xor, false);
                for (int j = 0; j + i < n; j++) {
                    xor[j] = init[j] != init[i + j];
                }
                for (int j = n - 1; j >= 0; j--) {
                    if (j == n - 1) {
                        next[i][j] = n;
                    } else {
                        next[i][j] = next[i][j + 1];
                    }
                    if (xor[j]) {
                        next[i][j] = j;
                    }
                }
            }
            long[][] way = new long[n][n];
            int[][] time = new int[n][n];
            int inf = (int) 1e9;
            SequenceUtils.deepFill(time, inf);
            way[0][0] = 1;
            time[0][0] = 1;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    if (j > i) {
                        way[i][j] += way[i][j - 1];
                        time[i][j] = Math.min(time[i][j], time[i][j - 1]);
                    }
                    way[i][j] %= mod;
                }
                for (int j = i; j < n; j++) {
                    if (j > i && s[i] == '0') {
                        //invalid
                        way[i][j] = 0;
                        time[i][j] = inf;
                    }
                }
                for (int j = i; j < n; j++) {
                    if (time[i][j] >= inf) {
                        continue;
                    }
                    int l = j + 1;
                    int r = (j - i) + l;
                    if (r < n && compare(i, j, l, r) > 0) {
                        r++;
                    }
                    if (r >= n || r != l && s[l] == '0') {
                        continue;
                    }
                    way[l][r] += way[i][j];
                    time[l][r] = Math.min(time[l][r], time[i][j] + 1);
                }
            }

            long totalWay = 0;
            int bestTail = 0;
            for (int i = 0; i < n; i++) {
                totalWay += way[i][n - 1];
                if (time[i][n - 1] < inf) {
                    //possible
                    if (compare(s, bestTail, time[bestTail][n - 1], i, time[i][n - 1]) > 0) {
                        bestTail = i;
                    }
                }
            }

            long minOp = 0;
            for (int i = bestTail; i < n; i++) {
                minOp = minOp * 2 + s[i] - '0';
                minOp %= mod;
            }
            minOp += time[bestTail][n - 1];

            totalWay = DigitUtils.mod(totalWay, mod);
            minOp = DigitUtils.mod(minOp, mod);
            out.println(totalWay);
            out.println(minOp);
        }

    }

    static class SequenceUtils {
        public static void deepFill(Object array, int val) {
            if (!array.getClass().isArray()) {
                throw new IllegalArgumentException();
            }
            if (array instanceof int[]) {
                int[] intArray = (int[]) array;
                Arrays.fill(intArray, val);
            } else {
                Object[] objArray = (Object[]) array;
                for (Object obj : objArray) {
                    deepFill(obj, val);
                }
            }
        }

    }

    static final class BitSet implements Serializable, Cloneable, Comparable<BitSet> {
        private long[] data;
        private long tailAvailable;
        private int capacity;
        private int m;
        private static final int SHIFT = 6;
        private static final int LOW = 63;
        private static final int BITS_FOR_EACH = 64;
        private static final long ALL_ONE = ~0L;
        private static final long ALL_ZERO = 0L;
        private static final int MAX_OFFSET = 63;
        private static long[] EMPTY_ARRAY = new long[0];

        public BitSet(int n) {
            capacity = n;
            this.m = (capacity + 64 - 1) / 64;
            data = new long[m];
            tailAvailable = oneBetween(0, offset(capacity - 1));
        }

        public BitSet(BitSet bs) {
            this.data = bs.data.clone();
            this.tailAvailable = bs.tailAvailable;
            this.capacity = bs.capacity;
            this.m = bs.m;
        }

        private BitSet(BitSet bs, int l, int r) {
            this.data = EMPTY_ARRAY;
            copyInterval(bs, l, r);
        }

        public void copyInterval(BitSet bs, int l, int r) {
            capacity = r - l + 1;
            tailAvailable = oneBetween(0, offset(capacity - 1));
            int reqLength = word(r) - word(l) + 1;
            if (data.length >= word(r) - word(l) + 1) {
                System.arraycopy(bs.data, word(l), data, 0, reqLength);
            } else {
                data = Arrays.copyOfRange(bs.data, word(l), word(r) + 1);
            }
            this.m = reqLength;
            leftShift(offset(l));
            this.m = (capacity + 64 - 1) / 64;
            data[m - 1] &= tailAvailable;
            for (int i = m; i < reqLength; i++) {
                data[i] = 0;
            }
        }

        private static int word(int i) {
            return i >>> SHIFT;
        }

        private static int offset(int i) {
            return i & LOW;
        }

        private long oneBetween(int l, int r) {
            if (r < l) {
                return 0;
            }
            long lBegin = 1L << offset(l);
            long rEnd = 1L << offset(r);
            return (ALL_ONE ^ (lBegin - 1)) & ((rEnd << 1) - 1);
        }

        public int capacity() {
            return capacity;
        }

        public int nextSetBit(int start) {
            int offset = offset(start);
            int w = word(start);
            if (offset != 0) {
                long mask = oneBetween(offset, MAX_OFFSET);
                if ((data[w] & mask) != 0) {
                    return Long.numberOfTrailingZeros(data[w] & mask) + w * BITS_FOR_EACH;
                }
                w++;
            }

            while (w < m && data[w] == ALL_ZERO) {
                w++;
            }
            if (w >= m) {
                return capacity();
            }
            return Long.numberOfTrailingZeros(data[w]) + w * BITS_FOR_EACH;
        }

        public void leftShift(int n) {
            int wordMove = word(n);
            int offsetMove = offset(n);
            int rshift = MAX_OFFSET - (offsetMove - 1);

            if (offsetMove != 0) {
                //slightly
                for (int i = 0; i < m; i++) {
                    if (i > 0) {
                        data[i - 1] |= data[i] << rshift;
                    }
                    data[i] >>>= offsetMove;
                }
            }
            if (wordMove > 0) {
                for (int i = 0; i < m; i++) {
                    if (i >= wordMove) {
                        data[i - wordMove] = data[i];
                    }
                    data[i] = 0;
                }
            }
        }

        public BitSet clone() {
            return new BitSet(this);
        }

        public String toString() {
            StringBuilder builder = new StringBuilder("{");
            for (int i = nextSetBit(0); i < capacity(); i = nextSetBit(i + 1)) {
                builder.append(i).append(',');
            }
            if (builder.length() > 1) {
                builder.setLength(builder.length() - 1);
            }
            builder.append("}");
            return builder.toString();
        }

        public int hashCode() {
            int ans = 1;
            for (int i = 0; i < m; i++) {
                ans = ans * 31 + Long.hashCode(data[i]);
            }
            return ans;
        }

        public boolean equals(Object obj) {
            if (!(obj instanceof BitSet)) {
                return false;
            }
            BitSet other = (BitSet) obj;
            if (other.capacity != capacity) {
                return false;
            }
            for (int i = 0; i < m; i++) {
                if (other.data[i] != data[i]) {
                    return false;
                }
            }
            return true;
        }

        public int compareTo(BitSet o) {
            if (capacity != o.capacity) {
                return Integer.compare(capacity, o.capacity);
            }
            return CompareUtils.compareArray(data, 0, m - 1,
                    o.data, 0, m - 1);
        }

    }

    static class CompareUtils {
        private CompareUtils() {
        }

        public static int compareArray(long[] a, int al, int ar, long[] b, int bl, int br) {
            for (int i = al, j = bl; i <= ar && j <= br; i++, j++) {
                if (a[i] != b[j]) {
                    return Long.compare(a[i], b[j]);
                }
            }
            return (ar - al) - (br - bl);
        }

    }

    static class FastInput {
        private final InputStream is;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 13);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastInput(InputStream is) {
            this.is = is;
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    bufLen = -1;
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public String rs() {
            return readString();
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int mod(long x, int mod) {
            if (x < -mod || x >= mod) {
                x %= mod;
            }
            if (x < 0) {
                x += mod;
            }
            return (int) x;
        }

    }

    static class FastOutput implements AutoCloseable, Closeable, Appendable {
        private static final int THRESHOLD = 32 << 10;
        private final Writer os;
        private StringBuilder cache = new StringBuilder(THRESHOLD * 2);

        public FastOutput append(CharSequence csq) {
            cache.append(csq);
            return this;
        }

        public FastOutput append(CharSequence csq, int start, int end) {
            cache.append(csq, start, end);
            return this;
        }

        private void afterWrite() {
            if (cache.length() < THRESHOLD) {
                return;
            }
            flush();
        }

        public FastOutput(Writer os) {
            this.os = os;
        }

        public FastOutput(OutputStream os) {
            this(new OutputStreamWriter(os));
        }

        public FastOutput append(char c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(long c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput append(String c) {
            cache.append(c);
            afterWrite();
            return this;
        }

        public FastOutput println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append(System.lineSeparator());
        }

        public FastOutput flush() {
            try {
//            boolean success = false;
//            if (stringBuilderValueField != null) {
//                try {
//                    char[] value = (char[]) stringBuilderValueField.get(cache);
//                    os.write(value, 0, cache.length());
//                    success = true;
//                } catch (Exception e) {
//                }
//            }
//            if (!success) {
                os.append(cache);
//            }
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
            return this;
        }

        public void close() {
            flush();
            try {
                os.close();
            } catch (IOException e) {
                throw new UncheckedIOException(e);
            }
        }

        public String toString() {
            return cache.toString();
        }

    }
}