<p>A program was supposed to print an array of integers. The program forgot to print whitespaces and the array is printed as a string of digits <code>s</code> and all we know is that all integers in the array were in the range <code>[1, k]</code> and there are no leading zeros in the array.</p>

<p>Given the string <code>s</code> and the integer <code>k</code>, return <em>the number of the possible arrays that can be printed as </em><code>s</code><em> using the mentioned program</em>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1000&quot;, k = 10000
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only possible array is [1000]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1000&quot;, k = 10
<strong>Output:</strong> 0
<strong>Explanation:</strong> There cannot be an array that was printed this way and has all integer &gt;= 1 and &lt;= 10.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;1317&quot;, k = 2000
<strong>Output:</strong> 8
<strong>Explanation:</strong> Possible arrays are [1317],[131,7],[13,17],[1,317],[13,1,7],[1,31,7],[1,3,17],[1,3,1,7]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>
	<li><code>s</code> consists of only digits and does not contain leading zeros.</li>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution {
public:
    int numberOfArrays(string s, int k) {
        long long curv = 0;
        int n_pos = 0;
        int n = s.size();
        vector<long long> dp(n+1);
        //queue<int> maxv;
        //vector<int> k_str;
        int k_ = k;
        long long nk = 0;
        while (k_) {
            //k_str.push_back(k_ % 10);
            k_ /= 10;
            nk++;
        }
        dp[0] = 1;
        dp[1] = 1;
        curv = s[0] - '0';
        if (curv > k) return 0;
        int constc = 1000000007;
        long long ten = 10;
        //cout << nk << endl;
        for (int i = 2; i <= n; i++) {
            curv = curv*ten+(long long)(s[i-1] - '0');
            //cout << curv << endl;
            if (s[i - 1] != '0') {
                dp[i] = dp[i-1]*2;

                if (curv > k) {
                    if (curv / (long long)(pow(ten,nk)) != 0) {
                        curv %= (long long)(pow(ten,nk));
                        //cout << i - nk - 1 << endl;
                        dp[i] -= dp[i - nk - 1];
                    }
                    if (curv > k) {
                        curv %= (long long)(pow(ten,nk - 1));
                        dp[i] -= dp[i - nk];
                    }
                }
            }
            else {
                dp[i] = dp[i-1];
                if (curv > k) {
                    if (curv / (long long)(pow(ten,nk)) != 0) {
                        curv %= (long long)(pow(ten,nk));
                        if (curv == 0) return 0;
                        //cout << i - nk - 1 << endl;
                        dp[i] -= dp[i - nk - 1];
                    }
                    if (curv > k) {
                        curv %= (long long)(pow(ten,nk-1));
                        if (curv == 0) return 0;
                        dp[i] -= dp[i - nk];
                    }
                }
            }
            //if (dp[])
            //if (curv == 0) return 0;
            dp[i] %= constc;
            
            //cout << dp[i] << endl;
        }
        if (dp[n] < 0) return dp[n] + constc;
        return dp[n];
    }
};
15818