1383_E. Strange Operation_28890
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.
import sys
readline = sys.stdin.readline

MOD = 10**9+7
S = readline().strip().split('1')
if len(S) == 1:
    print(len(S[0]))
else:
    S = [len(s)+1 for s in S]
    ans = S[0]*S[-1]
    S = S[1:-1]
    
    dp = [0]*(max(S)+2)
    dp[0] = 1
    for ai in S:
        res = 0
        rz = 0
        for i in range(ai+1):
            res = (res + dp[i])%MOD
            rz = (rz + (ai-i)*dp[i])%MOD
            dp[i] = 0
        dp[0] = rz
        dp[ai] = res
    aaa = 0
    for d in dp:
        aaa = (aaa+d)%MOD
    print(aaa*ans%MOD)
        
000
 0101
 00101100011100
 0001111
 0
 10100011001101100010000111001011
 01011111111101101100000100000000100000111001011011110110110010010001011110100011000011100100010001
 11
 00100
 0100111100100101001101111001011101011001111100110111101110001001010111100010011100011011101111010111111010010101000001110110111110010001100010101110111111000011101110000000001101010011000111111100000000000000001010011111010111
 10000011001101100010000111001011
 01011111111101101100000100000000100000111001011011110110110010010001011110100011000011100100110001
 00110
 0100111100100101001101111001001101011001111100110111101110001001010111100010011100011011101111010111111010010101000001110110111110010001100010101110111111000011101110000000001101010011000111111100000000000000001010011111010111
 010
 0111
 00101100111100
 1001111
 00000011001101100010000111001011
 01011111111101101100000100000000100000111001011011110110110110010001011110100011000011100100110001
 0100111100100101001101111001001101011001111100110111101110001001010111100010011100011011101111010111111010010101000001110110111110011001100010101110111111000011101110000000001101010011000111111100000000000000001010011111010111
 00001100111100
 0001101
 00000011001101100110000111001011
 01011111111101101100000100000000100000111001011011110110110110010001011110100011000011100000110001
 11110
 1101
 00000100111100
 0011111
 00000011001101100110010111001011
 01011111111101101100000100000000100000111001011011110110110110010001011110100011010011100000110001
 0100111100100101001101111101001101011001111100110111101110001001010111100010010100011011101111010111111010010101000001110110111110011001100010101110111111000011101110000000001101010011000111111100000000000000001010011111010111
 111
 00000110111100
 1001101
 01011111111101101100000100000000100000111001011011110110110110010001011110100011010011100000110101
 10111
 00001110111100
 1001100
 00000111001101100110010101001011
 01011111111101101100000100000000100000111001011011100110110110010001011110100011010011100000110101
 10110
 0100111100100101001101111101001101011001111100110111101110001001010111100010011100011011101111010111111010010101000001110110111110011001100010101110111110000011101110000000001101010011000111111100000000000000001010011111010111
 00011110111100
 1101100
 00000111001101100110000101001011
 01011111111101101100000100000000100000111001011011101110110110010001011110100011010011100000110101
 0100111100100101001101111101001101011001111100110111101110001001010101100010011100011011101111010111111010010101000001110110111110011001100010101110111110000011101110000000001101010011000111111100000000000000001010011111010111
 00011010111100
 1101110
 01011101111101101100000100000000100000111001011011101110110110010001011110100011010011100000110101
 01110
 011
 1111
 0100111100100101001101111001001101011001111100110111101110001001010111100010010100011011101111010111111010010101000001110110111110011001100010101110111111000011101110000000001101010011000111111100000000000000001010011111010111
 110
 11111
 1100
 00000011001101100110010101001011
 0100111100100101001101111101001101011001111100110111101110001001010111100010011100011011101111010111111010010101000001110110111110011001100010101110111111000011101110000000001101010011000111111100000000000000001010011111010111
 11010
 00000011001101100110000101001011
 11011

3
 6
 477
 16
 1
 259067
 911929203
 2
 9
 975171002
 155371
 98768341
 12
 732282420
 4
 6
 441
 13
 181265
 646636733
 94595540
 330
 20
 227318
 81831360
 8
 5
 234
 15
 245434
 483206834
 285824179
 3
 252
 16
 979556429
 7
 285
 21
 294522
 765659009
 10
 255671504
 288
 24
 272874
 659486563
 654765448
 348
 22
 758910981
 12
 4
 4
 94595540
 4
 5
 6
 245434
 285824179
 10
 227318
 8
