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.io.OutputStream;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.io.IOException;
import java.io.UncheckedIOException;
import java.io.Closeable;
import java.io.Writer;
import java.io.OutputStreamWriter;
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;
        SubstringCompare sc;

        public int compare(int l, int r, int L, int R) {
            return sc.compare(l, r, L, R);
        }

        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;
            sc = new SubstringCompare(new IntFunctionIntSequenceAdapter(i -> s[i], 0, n - 1));
            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 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 println(long c) {
            return append(c).println();
        }

        public FastOutput println() {
            return append('\n');
        }

        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();
        }

    }

    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 class SuffixArrayDC3 {
        static boolean leq(int a1, int a2, int b1, int b2) {
            return a1 < b1 || a1 == b1 && a2 <= b2;
        }

        static boolean leq(int a1, int a2, int a3, int b1, int b2, int b3) {
            return a1 < b1 || a1 == b1 && leq(a2, a3, b2, b3);
        }

        static void radixPass(int[] a, int[] b, int[] r, int offset, int n, int K) {
            int[] cnt = new int[K + 1];
            for (int i = 0; i < n; i++)
                ++cnt[r[a[i] + offset]];
            for (int i = 1; i < cnt.length; i++)
                cnt[i] += cnt[i - 1];
            for (int i = n - 1; i >= 0; i--)
                b[--cnt[r[a[i] + offset]]] = a[i];
        }

        private static void suffixArray(int[] T, int[] SA, int n, int K) {
            int n0 = (n + 2) / 3;
            int n1 = (n + 1) / 3;
            int n2 = n / 3;
            int n02 = n0 + n2;

            //******* Step 0: Construct sample ********
            // generate positions of mod 1 and mod 2 suffixes
            // the "+(n0-n1)" adds a dummy mod 1 suffix if n%3 == 1
            int[] R = new int[n02 + 3];
            for (int i = 0, j = 0; i < n + (n0 - n1); i++) if (i % 3 != 0) R[j++] = i;

            //******* Step 1: Sort sample suffixes ********
            // lsb radix sort the mod 1 and mod 2 triples
            int[] SA12 = new int[n02 + 3];
            radixPass(R, SA12, T, 2, n02, K);
            radixPass(SA12, R, T, 1, n02, K);
            radixPass(R, SA12, T, 0, n02, K);

            // find lexicographic names of triples and
            // write them to correct places in R
            int name = 0;
            for (int i = 0; i < n02; i++) {
                if (i == 0 || T[SA12[i]] != T[SA12[i - 1]] || T[SA12[i] + 1] != T[SA12[i - 1] + 1] || T[SA12[i] + 2] != T[SA12[i - 1] + 2]) {
                    ++name;
                }
                R[SA12[i] / 3 + (SA12[i] % 3 == 1 ? 0 : n0)] = name;
            }

            if (name < n02) {
                // recurse if names are not yet unique
                suffixArray(R, SA12, n02, name);
                // store unique names in R using the suffix array
                for (int i = 0; i < n02; i++)
                    R[SA12[i]] = i + 1;
            } else {
                // generate the suffix array of R directly
                for (int i = 0; i < n02; i++)
                    SA12[R[i] - 1] = i;
            }

            //******* Step 2: Sort nonsample suffixes ********
            // stably sort the mod 0 suffixes from SA12 by their first character
            int[] R0 = new int[n0];
            for (int i = 0, j = 0; i < n02; i++)
                if (SA12[i] < n0) R0[j++] = 3 * SA12[i];
            int[] SA0 = new int[n0];
            radixPass(R0, SA0, T, 0, n0, K);

            //******* Step 3: Merge ********
            // merge sorted SA0 suffixes and sorted SA12 suffixes
            for (int p = 0, t = n0 - n1, k = 0; k < n; k++) {
                int i = SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2; // pos of current offset 12 suffix
                int j = SA0[p]; // pos of current offset 0 suffix
                if (SA12[t] < n0 ? // different compares for mod 1 and mod 2 suffixes
                        leq(T[i], R[SA12[t] + n0], T[j], R[j / 3]) :
                        leq(T[i], T[i + 1], R[SA12[t] - n0 + 1], T[j], T[j + 1], R[j / 3 + n0])) { // suffix from SA12 is smaller
                    SA[k] = i;
                    if (++t == n02) // done --- only SA0 suffixes left
                        for (k++; p < n0; p++, k++)
                            SA[k] = SA0[p];
                } else { // suffix from SA0 is smaller
                    SA[k] = j;
                    if (++p == n0) // done --- only SA12 suffixes left
                        for (k++; t < n02; t++, k++)
                            SA[k] = SA12[t] < n0 ? SA12[t] * 3 + 1 : (SA12[t] - n0) * 3 + 2;
                }
            }
        }

        public static int[] suffixArray(IntSequence s) {
            int n = s.length();
            if (n <= 1)
                return new int[n];
            int[] S = IntStream.range(0, n + 3).map(i -> i < n ? s.get(i) : 0).toArray();
            int[] sa = new int[n];
            suffixArray(S, sa, n, 255);
            return sa;
        }

        public static int[] rank(int[] sa) {
            int[] inv = new int[sa.length];
            for (int i = 0; i < sa.length; i++) {
                inv[sa[i]] = i;
            }
            return inv;
        }

        public static int[] lcp(int[] sa, int[] rank, IntSequence s) {
            int n = sa.length;
            int[] lcp = new int[n - 1];
            for (int i = 0, h = 0; i < n; i++) {
                if (rank[i] < n - 1) {
                    for (int j = sa[rank[i] + 1]; Math.max(i, j) + h < s.length() && s.get(i + h) == s.get(j + h); ++h)
                        ;
                    lcp[rank[i]] = h;
                    if (h > 0)
                        --h;
                }
            }
            return lcp;
        }

    }

    static interface IntegerComparator {
        public int compare(int a, int b);

    }

    static class IntegerSparseTable {
        private int[][] st;
        private IntegerBinaryFunction merger;

        public IntegerSparseTable(IntToIntegerFunction function, int length, IntegerBinaryFunction merger) {
            int m = Log2.floorLog(length);
            st = new int[m + 1][length];
            this.merger = merger;
            for (int i = 0; i < length; i++) {
                st[0][i] = function.apply(i);
            }
            for (int i = 0; i < m; i++) {
                int interval = 1 << i;
                for (int j = 0; j < length; j++) {
                    if (j + interval < length) {
                        st[i + 1][j] = merge(st[i][j], st[i][j + interval]);
                    } else {
                        st[i + 1][j] = st[i][j];
                    }
                }
            }
        }

        private int merge(int a, int b) {
            return merger.apply(a, b);
        }

        public int query(int left, int right) {
            int queryLen = right - left + 1;
            int bit = Log2.floorLog(queryLen);
            // x + 2^bit == right + 1
            // So x should be right + 1 - 2^bit - left=queryLen - 2^bit
            return merge(st[bit][left], st[bit][right + 1 - (1 << bit)]);
        }

        public String toString() {
            return Arrays.toString(st[0]);
        }

    }

    static class Log2 {
        public static int floorLog(int x) {
            if (x <= 0) {
                throw new IllegalArgumentException();
            }
            return 31 - Integer.numberOfLeadingZeros(x);
        }

    }

    static interface IntegerBinaryFunction {
        int apply(int a, int b);

    }

    static class SubstringCompare {
        int[] sa;
        int[] lcp;
        int[] rank;
        RMQBeta rmq;

        public int lcpBetweenSuffix(int l, int L) {
            if (l == L) {
                return sa.length - l;
            }
            int r1 = rank[l];
            int r2 = rank[L];
            if (r1 > r2) {
                int tmp = r1;
                r1 = r2;
                r2 = tmp;
            }
            int bothLcp = lcp[rmq.query(r1, r2 - 1)];
            return bothLcp;
        }

        public SubstringCompare(IntSequence seq) {
            if (seq.length() <= 1) {
                sa = new int[1];
                rank = new int[1];
                lcp = new int[0];
                return;
            }
//        SAIS sais = new SAIS(seq);
//        sa = sais.rank2Index;
//        rank = sais.index2Rank;
//        lcp = sais.lcp;
            sa = SuffixArrayDC3.suffixArray(seq);
            rank = SuffixArrayDC3.rank(sa);
            lcp = SuffixArrayDC3.lcp(sa, rank, seq);
            rmq = new RMQBeta(lcp.length, (i, j) -> Integer.compare(lcp[i], lcp[j]));
        }

        public int compare(int l, int r, int L, int R) {
            if (l == L) {
                return Integer.compare(r, R);
            }
            int len1 = r - l + 1;
            int len2 = R - L + 1;
            int bothLcp = lcpBetweenSuffix(l, L);
            if (bothLcp >= len1 || bothLcp >= len2) {
                return Integer.compare(len1, len2);
            }
            return Integer.compare(rank[l], rank[L]);
        }

    }

    static class DigitUtils {
        private DigitUtils() {
        }

        public static int floorDiv(int a, int b) {
            return a < 0 ? -ceilDiv(-a, b) : a / b;
        }

        public static int ceilDiv(int a, int b) {
            if (a < 0) {
                return -floorDiv(-a, b);
            }
            int c = a / b;
            if (c * b < a) {
                return c + 1;
            }
            return c;
        }

        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 RMQBeta {
        int n;
        IntegerComparator comp;
        static int shift = 5;
        static int blockSize = 1 << shift;
        static int andMask = blockSize - 1;
        int[] minIndices;
        int[] toLeft;
        IntegerSparseTable st;

        private int min(int a, int b) {
            return comp.compare(a, b) <= 0 ? a : b;
        }

        public RMQBeta(int n, IntegerComparator comp) {
            this.comp = comp;
            this.n = n;
            minIndices = new int[DigitUtils.ceilDiv(n, blockSize)];
            Arrays.fill(minIndices, -1);
            for (int i = 0; i < n; i++) {
                int to = i >>> shift;
                if (minIndices[to] == -1 ||
                        comp.compare(minIndices[to], i) > 0) {
                    minIndices[to] = i;
                }
            }
            st = new IntegerSparseTable(i -> minIndices[i],
                    minIndices.length,
                    (a, b) -> comp.compare(a, b) <= 0 ? a : b);
            toLeft = new int[n];
            int mask = 0;
            for (int i = 0; i < n; i++) {
                if ((i & andMask) == 0) {
                    mask = 0;
                }
                int b = i >>> shift;
                while (mask != 0) {
                    int head = Bits.highestOneBitOffset(mask);
                    if (comp.compare(i, (b << shift) | head) <= 0) {
                        mask = Bits.clear(mask, head);
                    } else {
                        break;
                    }
                }
                mask = Bits.set(mask, i & andMask);
                toLeft[i] = mask;
            }
        }

        public int query(int l, int r) {
            assert l <= r;
            int bl = l >>> shift;
            int br = r >>> shift;
            int tl = l & andMask;
//        int tr = r & andMask;
            if (bl == br) {
                return Integer.numberOfTrailingZeros(toLeft[r] & Bits.tailIntMask(32 - tl)) | (bl << shift);
            }
            int res1 = Integer.numberOfTrailingZeros(toLeft[(bl << shift) | andMask] & Bits.tailIntMask(32 - tl)) | (bl << shift);
            int res2 = Integer.numberOfTrailingZeros(toLeft[r]) | (br << shift);
            int best = min(res1, res2);
            if (bl + 1 < br) {
                best = min(best, st.query(bl + 1, br - 1));
            }
            return best;
        }

    }

    static interface IntToIntegerFunction {
        int apply(int x);

    }

    static class IntFunctionIntSequenceAdapter implements IntSequence {
        IntToIntegerFunction data;
        int l;
        int r;

        public IntFunctionIntSequenceAdapter(IntToIntegerFunction data, int l, int r) {
            this.data = data;
            this.l = l;
            this.r = r;
        }

        public int get(int i) {
            return data.apply(l + i);
        }

        public int length() {
            return r - l + 1;
        }

    }

    static interface IntSequence extends Comparable<IntSequence> {
        int get(int i);

        int length();

        default int compareTo(IntSequence o) {
            int n = length();
            int m = o.length();
            for (int i = 0, to = Math.min(n, m); i < to; i++) {
                int ans = Integer.compare(get(i), o.get(i));
                if (ans != 0) {
                    return ans;
                }
            }
            return Integer.compare(n, m);
        }

    }

    static class Bits {
        private Bits() {
        }

        public static int set(int x, int i) {
            return x | (1 << i);
        }

        public static int clear(int x, int i) {
            return x & (~(1 << i));
        }

        public static int highestOneBitOffset(int x) {
            return 31 - Integer.numberOfLeadingZeros(x);
        }

        public static int tailIntMask(int n) {
            if (n == 0) {
                return 0;
            }
            return -1 << (32 - n);
        }

    }

    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);
        }

    }
}