VOI - OR - 4 subs

//Make CSP great again
//You're as beautiful as the day I lost you
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int mod = 1e9 + 7, N = 1e6, M = 200;
int f[M + 1][1000], dp[N + 1], cnt[N + 1], a[N + 1], fac[N + 1], MaxA, n, L, R, k;
void read()
{
    cin >> n >> k >> L >> R;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        ++cnt[a[i]];
        MaxA = max(MaxA, a[i]);
    }
}
void Sub2()
{
    f[0][0] = 1;
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = k - 1; j >= 0; -- j)
        {
            for (int mask = 0; mask < (1 << 8); ++ mask)
            {
                f[j + 1][mask | a[i]] += f[j][mask];
                f[j + 1][mask | a[i]] %= mod;
            }
        }
    }
    int res = 0;
    for (int i = (L + 2)/3 * 3; i <= min(255, R); i += 3)
    {
        res += f[k][i];
        res %= mod;
    }
    cout << res;
}
int Pow(int a, int b)
{
    int ret = 1;
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
        {
            ret = (1LL * ret * a) % mod;
        }
        a = (1LL * a * a) % mod;
    }
    return ret;
}
int C(int k, int n)
{
    if (k > n)
    {
        return 0;
    }
    return (1LL * ((1LL * fac[n] * Pow(fac[n - k], mod - 2)) % mod) * Pow(fac[k], mod - 2)) % mod;;
}
void Sub4()
{
    if (L % 3 != 0)
    {
        cout << 0;
        return ;
    }
    fac[0] = 1;
    for (int i = 1; i <= N; ++ i)
    {
        fac[i] = (1LL * fac[i - 1] * i) % mod;
    }
    for (int i = 0; i <= N; ++ i)
    {
        dp[i] = cnt[i];
    }
    for (int i = 0; i < 20; ++ i)
    {
        for (int mask = (1 << 20) - 1; mask >= 0; -- mask)
        {
            if ((mask >> i) & 1)
            {
                dp[mask] += dp[mask ^ (1 << i)];
            }
        }
    }
    int res = 0;
    int x = __builtin_popcount(L);
    for (int mask = L; mask > 0; mask = (mask - 1) & L)
    {
        int t = abs(x - __builtin_popcount(mask)) & 1;
        if (t == 0)
        {
            res += C(k, dp[mask]);
            res %= mod;
        }
        else
        {
            res -= C(k, dp[mask]);
            res %= mod;
        }
    }
    cout << (res + mod) % mod;
}
void solve()
{
    if (n <= M && MaxA <= M)
    {
        Sub2();
        return ;
    }
    if (L == R)
    {
        Sub4();
        return;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}