Problem: Koa the Koala has a binary string s of length n. Koa can perform no more than n-1 (possibly zero) operations of the following form:

In one operation Koa selects positions i and i+1 for some i with 1 ≤ i < |s| and sets s_i to max(s_i, s_{i+1}). Then Koa deletes position i+1 from s (after the removal, the remaining parts are concatenated).

Note that after every operation the length of s decreases by 1.

How many different binary strings can Koa obtain by doing no more than n-1 (possibly zero) operations modulo 10^9+7 (1000000007)?

Input

The only line of input contains binary string s (1 ≤ |s| ≤ 10^6). For all i (1 ≤ i ≤ |s|) s_i = 0 or s_i = 1.

Output

On a single line print the answer to the problem modulo 10^9+7 (1000000007).

Examples

Input


000


Output


3


Input


0101


Output


6


Input


0001111


Output


16


Input


00101100011100


Output


477

Note

In the first sample Koa can obtain binary strings: 0, 00 and 000.

In the second sample Koa can obtain binary strings: 1, 01, 11, 011, 101 and 0101. For example:

  * to obtain 01 from 0101 Koa can operate as follows: 0101 → 0(10)1 → 011 → 0(11) → 01. 
  * to obtain 11 from 0101 Koa can operate as follows: 0101 → (01)01 → 101 → 1(01) → 11. 



Parentheses denote the two positions Koa selected in each operation.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.math.*;

public class E {
    static final boolean RUN_TIMING = false;
    static char[] inputBuffer = new char[1 << 20];
    static PushbackReader in = new PushbackReader(new BufferedReader(new InputStreamReader(System.in)), 1 << 20);
    static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    long MOD = 1000000007;

    public void go() throws IOException {
        // in = new PushbackReader(new BufferedReader(new FileReader(new File("test.txt"))), 1 << 20);
        // out = new PrintWriter(new FileWriter(new File("output.txt")));
        String ss = spar();
        
        // HashSet<String> set = new HashSet<>();
        // bruteForce(ss, set);

        int lastOne = ss.lastIndexOf('1');
        int firstOne = ss.indexOf('1');
        if (lastOne == -1) {
            out.println(ss.length());
            return;
        }

        int suffix = ss.length() - lastOne - 1;
        int prefix = firstOne;
        char[] s = ss.substring(firstOne, lastOne+1).toCharArray();
        int n = s.length;

        int[] dist = new int[n];
        dist[0] = s[0] == '0' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            dist[i] = s[i] == '0' ? dist[i-1]+1 : 0;
        }
        // out.println(s);
        // out.println(Arrays.toString(dist));

        long[] dp = new long[n];
        int[] next = new int[n+2];
        Arrays.fill(next, n);
        for (int i = n-1; i >= 0; i--) {
            if (s[i] == '1') {
                dp[i] = 1;
            }
            dp[i] += next[0] < n ? dp[next[0]] : 0;
            dp[i] += next[dist[i]+1] < n ? dp[next[dist[i]+1]] : 0;
            dp[i] %= MOD;
            next[dist[i]] = i;
        }
        // out.println(Arrays.toString(dp));

        long ans = dp[0] * (suffix+1) % MOD * (prefix+1) % MOD;
        // out.printf("%d %d %d%n", dp[0], suffix, prefix);

        // if (set.size() != ans) {
        //     out.println("WRONG ANSWER");
        //     out.println(new TreeSet<>(set) + " = " + set.size());
        // }

        out.println(ans);
    }

    public void bruteForce(String s, HashSet<String> set) {
        set.add(s);
        for (int i = 0; i < s.length()-1; i++) {
            if (s.charAt(i) == '1' || s.charAt(i+1) == '1') {
                bruteForce(s.substring(0, i) + "1" + s.substring(i+2, s.length()), set);
            } else {
                bruteForce(s.substring(0, i) + "0" + s.substring(i+2, s.length()), set);
            }
        }
    }

    public int ipar() throws IOException {
        return Integer.parseInt(spar());
    }

    public int[] iapar(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = ipar();
        }
        return arr;
    }

    public long lpar() throws IOException {
        return Long.parseLong(spar());
    }

    public long[] lapar(int n) throws IOException {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = lpar();
        }
        return arr;
    }

    public double dpar() throws IOException {
        return Double.parseDouble(spar());
    }

    public String spar() throws IOException {
        int len = 0;
        int c;
        do {
            c = in.read();
        } while (Character.isWhitespace(c) && c != -1);
        if (c == -1) {
            throw new NoSuchElementException("Reached EOF");
        }
        do {
            inputBuffer[len] = (char)c;
            len++;
            c = in.read();
        } while (!Character.isWhitespace(c) && c != -1);
        while (c != '\n' && Character.isWhitespace(c) && c != -1) {
            c = in.read();
        }
        if (c != -1 && c != '\n') {
            in.unread(c);
        }
        return new String(inputBuffer, 0, len);
    }

    public String linepar() throws IOException {
        int len = 0;
        int c;
        while ((c = in.read()) != '\n' && c != -1) {
            if (c == '\r') {
                continue;
            }
            inputBuffer[len] = (char)c;
            len++;
        }
        return new String(inputBuffer, 0, len);
    }

    public boolean haspar() throws IOException {
        String line = linepar();
        if (line.isEmpty()) {
            return false;
        }
        in.unread('\n');
        in.unread(line.toCharArray());
        return true;
    }

    public void shuffle(int[] arr) throws IOException {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int j = (int)(Math.random() * (n-i) + i);
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public void shuffle(long[] arr) throws IOException {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int j = (int)(Math.random() * (n-i) + i);
            long temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public void shuffle(Object[] arr) throws IOException {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int j = (int)(Math.random() * (n-i) + i);
            Object temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    public static void main(String[] args) throws IOException {
        long time = 0;
        time -= System.nanoTime();
        new E().go();
        time += System.nanoTime();
        if (RUN_TIMING) {
            System.out.printf("%.3f ms%n", time / 1000000.0);
        }
        out.flush();
        in.close();
    }
}