Proficient.
Put your skills to the test.

Problem summary

A monkey independently types 0 with probability pA/pB and 1 otherwise, stopping when a fixed binary pattern S first appears as a suffix. Compute the expected number of keystrokes modulo 1,000,000,007.

Constraints

1 ≤ N ≤ 10⁷; 1 ≤ pA < pB < 1,000,000,007.

Worked example

An independently prepared example for this explanation.

4
3 4
1011

333333425

Solution analysis

1. For a pattern in an independent symbol stream, the expected waiting time is the sum of 1/Pr(prefix of length k) over all nonempty borders k of the full pattern, including k=N. A border is a prefix that is also a suffix. Overlapping occurrences account for the shorter-border terms.
2. Compute the KMP prefix-function array. Starting at length N, repeatedly replace the length by pi[length−1] to enumerate every nonempty border. Also scan S once to store inverseProbability[k]: multiply by pB/pA for each 0 and pB/(pB−pA) for each 1, performing division by modular inversion.
3. For S=1011 with p(0)=3/4, the nonempty border lengths are 4 and 1. Their reciprocal probabilities are 256/3 and 4; the expectation is 268/3, represented by 333333425 modulo the prime. Only two inversions are required; every prefix probability and the border sum are then updated by multiplication and addition.

Why it works

Start a hypothetical fair gambler with one unit immediately before each keystroke. It bets its entire fortune on the successive symbols of S, receiving a factor 1/p for a correct symbol and losing everything otherwise. At the stopping time, the surviving gamblers correspond exactly to suffixes equal to prefixes of S, namely its borders, with fortunes equal to reciprocal prefix probabilities. Fairness makes expected total final fortune equal to the expected number of unit stakes, which is the expected stopping time. The expectation is finite because disjoint length-N blocks each have positive chance to equal S, justifying the stopping identity. KMP lists exactly the borders, and modular arithmetic evaluates this rational identity since both symbol probabilities have nonzero denominators modulo the prime.

Watch out. Include the full pattern as a border. Do not ignore self-overlaps. Both symbol probabilities are nonzero modulo the prime under the stated bounds.

An independently written complete program with standard headers.

#include<iostream>
#include<string>
#include<vector>
// Algorithm: For a pattern in an independent symbol stream, the expected waiting time is the sum
// of 1/Pr(prefix of length k) over all nonempty borders k of the full pattern, including k=N.
using namespace std;
const long long mod=1000000007;
long long power(long long base,long long exponent){
    long long result=1;
    while(exponent>0){
        if(exponent&1){
            result=result*base%mod;
        }
        base=base*base%mod;
        exponent>>=1;
    }
    return result;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long numerator,denominator;
    string pattern;
    cin>>n>>numerator>>denominator>>pattern;
    long long inverseZero=denominator*power(numerator,mod-2)%mod;
    long long inverseOne=denominator*power(denominator-numerator,mod-2)%mod;
    vector<int>border(n),inverseProbability(n+1);
    inverseProbability[0]=1;
    for(int i=0;i<n;++i){
        inverseProbability[i+1]=
            static_cast<int>(inverseProbability[i]*(pattern[i]=='0'?inverseZero:inverseOne)%mod);
        if(i>0){
            int length=border[i-1];
            while(length>0&&pattern[i]!=pattern[length]){
                length=border[length-1];
            }
            if(pattern[i]==pattern[length]){
                ++length;
            }
            border[i]=length;
        }
    }
    long long answer=0;
    for(int length=n;length>0;length=border[length-1]){
        answer=(answer+inverseProbability[length])%mod;
    }
    cout<<answer<<'\n';
}