c.cpp

#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")

#include <stdio.h>
#include <bits/stdc++.h>
#include <x86intrin.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T1, typename T2> using ordered_map = tree<T1, T2, std::less<T1>, rb_tree_tag, tree_order_statistics_node_update>;

using namespace std;


#define pb push_back
#define ppb pop_back
#define mp make_pair
#define fs first
#define sc second
#define abs(a) ((a) < 0 ? -(a) : (a))
#define sqr(a) ((a) * (a))

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

inline pair<pair<bool, bool>, pair<string, bool> > useinout();

#ifdef SOL
double starttime;
#endif

void initialization() {
#ifdef SOL
    starttime = 1000. * clock() / CLOCKS_PER_SEC;
    if (useinout().fs.fs)
        freopen("input.txt", "r", stdin);
    if (useinout().fs.sc)
        freopen("output.txt", "w", stdout);
#else
    srand(__rdtsc());
    const string file = useinout().sc.fs;
    if (!file.empty()) {
        freopen((file + ".in").c_str(), "r", stdin);
        freopen((file + ".out").c_str(), "w", stdout);
    } else
    if(useinout().sc.sc) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
#endif
}

int solution();

void finish(int exitval) {
    fflush(stdout);
#ifdef SOL
    fprintf(stderr, "\n-----------------\nexit value: %d\ntime: %.3lf ms\n-----------------\n", exitval, 1000. * clock() / CLOCKS_PER_SEC - starttime);
#endif
}

int main() {
    initialization();
    finish(solution());
    return (0);
}

const double eps = 1e-9;
const int mod = (int) 1e+9 + 7;
const double pi = acos(-1.);
const int maxn = 1000100;


ll binpow(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = ret * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ret;
}

ll dp[maxn];
unordered_map<ll, ll> pd;

ll rec(ll n, ll k, ll a, ll b) {
    if(n <= 1e5)
        return dp[n];
    if(pd.count(n)) return pd[n];
    int ps[360] = {};
    ll ret = 0;
    ll ai = 1, aj = 1;
    for(int j = 0; j <= k; j++) {
        ps[j] = ((j ? ps[j - 1] : 0) + rec((n + 1) / 2 - j - 1, k, a, b) % mod * aj % mod * b % mod) % mod;
        aj = aj * a % mod;
    }
    for(int i = 0; i < k; i++) {
        ret = (ret + rec(n / 2 - i - 1, k, a, b) * ai % mod * b % mod * ps[k - 1 - i] % mod) % mod;
        ai = ai * a % mod;
    }
    return pd[n] = ret;
}

int solution() {

    ll n, k, a, b;
    scanf("%lld%lld%lld%lld", &n, &k, &a, &b);

    ll ak = binpow(a, k);
    dp[0] = 1;
    for(int i = 1; i < k; i++)
        dp[i] = dp[i - 1] * (a + b) % mod;
    dp[k] = (binpow(a + b, k) + mod - ak) % mod;
    for(int i = k + 1; i <= min(n, (ll)1e6 + 5); i++)
        dp[i] = (dp[i - 1] * (a + b) - dp[i - k - 1] * b % mod * ak) % mod;

    if(k > 350) {
        ll ans = (binpow(a + b, n) + mod - dp[n]) % mod;
        printf("%lld\n", ans);
    } else {
        ll ans = (binpow(a + b, n) + mod - rec(n, k, a, b)) % mod;
        printf("%lld\n", ans);
    }

    return (0);
}

inline pair<pair<bool, bool>, pair<string, bool> > useinout() {
    return (mp(mp(0, 0), mp("", 0)));
}

//by Andrey Kim