LOJ

分析

设 $f_i$ 表示 $n=i$ 时的答案，容易得到
$$
f_i=\sum_{j=0}^{i-1}f_jF_{i-j}
$$
然后推一推式子
$$
\begin{aligned}
xf_{i+1}-af_i&=\left(x\sum_{j=0}^if_jF_{i-j+1}\right)-\left(a\sum_{j=0}^{i-1}f_jF_{i-j}\right)\\
&=xf_iF_1+\left(x\sum_{j=0}^{i-1}f_jF_{i-j+1}\right)-\left(a\sum_{j=0}^{i-1}f_jF_{i-j}\right)\\
&=xf_i+\left(x\sum_{j=0}^{i-1}f_j\times\frac{aF_{i-j}+bF_{i-j-1}}{x}\right)-\left(a\sum_{j=0}^{i-1}f_jF_{i-j}\right)\\
&=xf_i+\left(a\sum_{j=0}^{i-1}f_jF_{i-j}\right)+\left(b\sum_{j=0}^{i-1}f_jF_{i-j-1}\right)-\left(a\sum_{j=0}^{i-1}f_jF_{i-j}\right)\\
&=xf_i+\left(b\sum_{j=0}^{i-2}f_jF_{i-j-1}\right)+bf_{i-1}F_0\\
&=xf_i+bf_{i-1}
\end{aligned}
$$
所以
$$
f_i=\frac{x+a}{x}\times f_{i-1}+\frac{b}{x}\times f_{i-2}
$$
所以
$$
f_i\equiv (x+a)x^{-1}\times f_{i-1}+bx^{-1}\times f_{i-2}\pmod{10^9+7}
$$
直接矩阵快速幂即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int mod=1e9+7;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

ll n; int x,a,b;

struct Matrix {
    int s[2][2];
    Matrix() { s[0][0]=s[0][1]=s[1][0]=s[1][1]=0; }
    int* operator [](int i) { return s[i]; }
} A,Q;

Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (re int i=0;i<2;++i)
        for (re int k=0;k<2;++k)
            for (re int j=0;j<2;++j)
                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j])%mod;
    return c;
}

inline Matrix qpow(Matrix a,ll b) {
    Matrix c; c[0][0]=c[1][1]=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    n=read(),x=read(),a=read(),b=read();
    A[0][0]=Q[0][1]=1,A[0][1]=Q[1][1]=0;
    Q[0][0]=1ll*(a+x)*qpow(x,mod-2)%mod;
    Q[1][0]=1ll*b*qpow(x,mod-2)%mod;
    printf("%d\n",(A*qpow(Q,n-1))[0][0]);
    return 0;
}