VOI21_OR

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

constexpr bool typetest = 0;
constexpr int N = 2e6 + 5;
constexpr ll mod = 1e9 + 7;
int n, k, l, r;
int cnt[N];
ll dp[N], gt[N], rgt[N], ans(0);

void Read()
{
    cin >> n >> k >> l >> r;
    for (int i = 1; i <= n; ++i)
    {
        int v;
        cin >> v;
        ++cnt[v];
    }
}

ll Pow(ll a, ll b)
{
    ll ans(1);
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}

ll C(int k, int n)
{
    if (k > n)
        return 0;
    return gt[n] * rgt[k] % mod * rgt[n - k] % mod;
}

#define bit(i, x) (((x) >> (i)) & 1)

void Solve()
{
    gt[0] = rgt[0] = 1;
    for (int i = 1; i < N; ++i)
    {
        gt[i] = gt[i - 1] * i % mod;
        rgt[i] = Pow(gt[i], mod - 2);
    }
    for (int i = 0; i < 20; ++i)
        for (int j = 0; j < (1 << 20); ++j)
            if (bit(i, j))
                cnt[j] += cnt[j ^ (1 << i)];

    for (int i = 0; i < (1 << 20); ++i)
        dp[i] = C(k, cnt[i]) * ((__builtin_popcount(i) & 1) ? 1 : -1);

    for (int i = 0; i < 20; ++i)
        for (int j = 0; j < (1 << 20); ++j)
            if (bit(i, j))
                (dp[j] += dp[j ^ (1 << i)]) %= mod;

    for (int i = l; i <= r; ++i)
        if (i % 3 == 0)
            (ans += ((__builtin_popcount(i) & 1) ? dp[i] : -dp[i])) %= mod;
    cout << (ans + mod) % mod;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}