/*
Nishant Gupta
nishant_141077
MNNIT Allahabad
*/
#include<bits/stdc++.h>
#define LL long long int
using namespace std;
int niceness[50], n;
vector<int> first_half[20];
vector<int> sec_half[20];
void generate_subsets_first(int st, int end) {
LL i = 0, j, sum = 0;
LL mask;
LL size = end - st + 1;
for(mask=0;mask<(1<<size);mask++) {
sum = 0;i = 0;
for(j=0;j<size;j++) {
if(!((1<<j)&mask)) {
sum += niceness[j];
i++;
}
}
first_half[i].push_back(sum);
}
}
void generate_subsets_second(int st, int end) {
LL i = 0, j, sum = 0;
LL mask;
LL size = end - st + 1;
for(mask=0;mask<(1<<size);mask++) {
sum = 0;i = 0;
for(j=0;j<size;j++) {
if(!((1<<j)&mask)) {
sum += niceness[st+j];
i++;
}
}
sec_half[i].push_back(sum);
}
}
int main() {
int i, j, k, a, b, x;
cin>>n>>k>>a>>b;
for(i=0;i<n;i++) {
cin>>x;
niceness[i] = 1;
for(j=2;j*j<=x;j++) {
if(x%j == 0) {
niceness[i] = niceness[i]*j;
}
while(x%j == 0) {
x/=j;
}
}
if(x > 1) {
niceness[i] = niceness[i]*x;
}
}
int mid = (n-1)/2;
int size = n - mid -1;
generate_subsets_first(0, mid);
generate_subsets_second(mid+1, n-1);
for(i=0;i<=size;i++) {
sort(sec_half[i].begin(), sec_half[i].end());
}
int t;
LL ans = 0;
for(i=0;i<=mid+1;i++) {
for(j=0;j<first_half[i].size();j++) {
int sum = first_half[i][j];
int upto = min(k-i, size);
int copy = ans;
for(t=0;t<=upto;t++) { //length of subsets in second half
int upper = upper_bound(sec_half[t].begin(), sec_half[t].end(), b-sum) - sec_half[t].begin();
int lower = lower_bound(sec_half[t].begin(), sec_half[t].end(), a-sum) - sec_half[t].begin();
ans = ans + (upper -lower);
}
}
}
cout<<ans<<endl;
return 0;
}
LyoKCU5pc2hhbnQgR3VwdGEKCW5pc2hhbnRfMTQxMDc3CglNTk5JVCBBbGxhaGFiYWQKKi8KCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgTEwgbG9uZyBsb25nIGludAp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmludCBuaWNlbmVzc1s1MF0sIG47CnZlY3RvcjxpbnQ+IGZpcnN0X2hhbGZbMjBdOwp2ZWN0b3I8aW50PiBzZWNfaGFsZlsyMF07Cgp2b2lkIGdlbmVyYXRlX3N1YnNldHNfZmlyc3QoaW50IHN0LCBpbnQgZW5kKSB7CglMTCBpID0gMCwgaiwgc3VtID0gMDsKCUxMIG1hc2s7CglMTCBzaXplID0gZW5kIC0gc3QgKyAxOwoJZm9yKG1hc2s9MDttYXNrPCgxPDxzaXplKTttYXNrKyspIHsKCQlzdW0gPSAwO2kgPSAwOwoJCWZvcihqPTA7ajxzaXplO2orKykgewoJCQlpZighKCgxPDxqKSZtYXNrKSkgewoJCQkJc3VtICs9IG5pY2VuZXNzW2pdOwoJCQkJaSsrOwoJCQl9CgkJfQoJCWZpcnN0X2hhbGZbaV0ucHVzaF9iYWNrKHN1bSk7Cgl9Cn0KCnZvaWQgZ2VuZXJhdGVfc3Vic2V0c19zZWNvbmQoaW50IHN0LCBpbnQgZW5kKSB7CglMTCBpID0gMCwgaiwgc3VtID0gMDsKCUxMIG1hc2s7CglMTCBzaXplID0gZW5kIC0gc3QgKyAxOwoJZm9yKG1hc2s9MDttYXNrPCgxPDxzaXplKTttYXNrKyspIHsKCQlzdW0gPSAwO2kgPSAwOwoJCWZvcihqPTA7ajxzaXplO2orKykgewoJCQlpZighKCgxPDxqKSZtYXNrKSkgewoJCQkJc3VtICs9IG5pY2VuZXNzW3N0K2pdOwoJCQkJaSsrOwoJCQl9CgkJfQoJCXNlY19oYWxmW2ldLnB1c2hfYmFjayhzdW0pOwoJfQp9CgppbnQgbWFpbigpIHsKCWludCBpLCBqLCBrLCBhLCBiLCB4OwoJY2luPj5uPj5rPj5hPj5iOwoJZm9yKGk9MDtpPG47aSsrKSB7CgkJY2luPj54OwoJCW5pY2VuZXNzW2ldID0gMTsKCQlmb3Ioaj0yO2oqajw9eDtqKyspIHsKCQkJaWYoeCVqID09IDApIHsKCQkJCW5pY2VuZXNzW2ldID0gbmljZW5lc3NbaV0qajsKCQkJfQoJCQl3aGlsZSh4JWogPT0gMCkgewoJCQkJeC89ajsKCQkJfQoJCX0KCQlpZih4ID4gMSkgewoJCQluaWNlbmVzc1tpXSA9IG5pY2VuZXNzW2ldKng7CgkJfQoJfQoJCglpbnQgbWlkID0gKG4tMSkvMjsKCWludCBzaXplID0gbiAtIG1pZCAtMTsKCWdlbmVyYXRlX3N1YnNldHNfZmlyc3QoMCwgbWlkKTsKCWdlbmVyYXRlX3N1YnNldHNfc2Vjb25kKG1pZCsxLCBuLTEpOwoKCWZvcihpPTA7aTw9c2l6ZTtpKyspIHsKCQlzb3J0KHNlY19oYWxmW2ldLmJlZ2luKCksIHNlY19oYWxmW2ldLmVuZCgpKTsKCX0KCWludCB0OwoJTEwgYW5zID0gMDsKCWZvcihpPTA7aTw9bWlkKzE7aSsrKSB7CgkJZm9yKGo9MDtqPGZpcnN0X2hhbGZbaV0uc2l6ZSgpO2orKykgewoJCQlpbnQgc3VtID0gZmlyc3RfaGFsZltpXVtqXTsKCQkJaW50IHVwdG8gPSBtaW4oay1pLCBzaXplKTsKCQkJaW50IGNvcHkgPSBhbnM7CgkJCWZvcih0PTA7dDw9dXB0bzt0KyspIHsgIC8vbGVuZ3RoIG9mIHN1YnNldHMgaW4gc2Vjb25kIGhhbGYKCQkJCWludCB1cHBlciA9IHVwcGVyX2JvdW5kKHNlY19oYWxmW3RdLmJlZ2luKCksIHNlY19oYWxmW3RdLmVuZCgpLCBiLXN1bSkgLSBzZWNfaGFsZlt0XS5iZWdpbigpOwoJCQkJaW50IGxvd2VyID0gbG93ZXJfYm91bmQoc2VjX2hhbGZbdF0uYmVnaW4oKSwgc2VjX2hhbGZbdF0uZW5kKCksIGEtc3VtKSAtIHNlY19oYWxmW3RdLmJlZ2luKCk7CgkJCQlhbnMgPSBhbnMgKyAodXBwZXIgLWxvd2VyKTsgCgkJCX0KCQl9Cgl9Cgljb3V0PDxhbnM8PGVuZGw7CglyZXR1cm4gMDsKfQ==