#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll a[2010];
ll pro[2010][2010]; // [v][cnt] 结果 <= v 的有cnt个的概率
ll c[2010][2010];

ll mypow(ll v,ll pwr){
  v=(v+MOD)%MOD;
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

// C(m,n) = m!/(n!(m-n)!)
ll C(ll m,ll n){
  if(n > m)return 0;
  return c[m][n];
}

int main(){
  rep(i,1,2005){
    c[i][0] = c[i][i] = 1;
    rep(j,1,i){
      c[i][j] = (c[i-1][j-1] + c[i-1][j])%MOD;
    }
  }

  ll n,m,k,x;
  cin>>n>>m>>k>>x;
  ll invm = mypow(m,MOD-2);
  x--; // 先减1
  rep(i,0,n){
    scanf("%lld",a+i);
  }
  sort(a,a+n);
  rep(v,1,m+1){
    int stx = 0;
    rep(i,0,n){
      if(a[i] <= v)stx++;
      else break;
    }
    if(stx == x){ // 结果必定 x
      pro[v][x] = 1;
      continue;
    }
    // p = v/m
    ll p = v * invm %MOD;
    rep(endx,0,n+1){
      if(stx < x){ // stx <= endx <= x
        if(stx <= endx && endx < x){
          // C(k,endx-stx) * p^(endx-stx) * (1-p)^(k-(endx-stx))
          pro[v][endx] = C(k,endx-stx) * mypow(p,endx-stx) %MOD * mypow(1-p,k-(endx-stx)) % MOD;
        }
      }else { // stx > x => stx >= endx >= x
        if(stx >= endx && endx > x){
          // C(k,stx-endx) * (1-p)^(stx-endx) * p^(k-(stx-endx))
          pro[v][endx] = C(k,stx-endx) * mypow(1-p,stx-endx) %MOD * mypow(p,k-(stx-endx)) % MOD;
        }
      }
    }
    // 最后处理 (endx == x) , 等于 1-其它概率和
    pro[v][x] = 1;
    rep(endx,0,n+1){
      if(endx == x)continue;
      (pro[v][x] -= pro[v][endx])%=MOD;
    }
  }
  ll leqv[2010] = {0};
  ll ans = 0;
  rep(v,1,m+1){
    rep(cnt,0,n+1){
      (leqv[v] += cnt*pro[v][cnt]%MOD)%=MOD; // 期望长度 = sum{期望*长度}
    }
    (ans += v*(leqv[v] - leqv[v-1]) %MOD)%=MOD; // count( == v) = count(<= v) - count(<= v-1)
  }
  printf("%lld\n", ((ans * mypow(m,k)%MOD)+MOD)%MOD); // 频次 = 总次数 * 频率
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->a;)
#define pb push_back
const double pi = acos(-1.0);

// 0 < a1 < a2 < a3..an 传送点
// 传送消耗 (ai-aj)**2 能量
// + 一些整数点 => a0 -> an 能量消耗 <= m
// 最小整数点个数

ll a[200010];
vector<ll> segs ;
int n;
ll m;

ll f(ll len, ll part){
  if(part > len)return len;
  ll minv = len/part;
  ll maxcnt = len%part;
  // printf("f(%lld %lld) => %lld %lld => %lld\n",len,part,minv,maxcnt,minv*minv*(part - maxcnt) + (minv+1)*(minv+1) * maxcnt);
  return minv*minv*(part - maxcnt) + (minv+1)*(minv+1) * maxcnt;
}

// 大于等于x的贡献都选
pair<ll,ll> calc(ll x){ // 切割次数, 消耗平方值
  assert(x > 0);
  ll cnt = 0; // 个数
  ll sum = 0; // 消耗
  rep(i,0,n){
    if(x <= 2){
      sum += f(segs[i],1) - f(segs[i],segs[i]); // 1*1*segs[i];
      cnt += segs[i] - 1;
      continue;
    }
    // 最大的都不满足
    if(f(segs[i],1) - f(segs[i],2) < x){
      continue;
    }
    // 二分切割的段
    int l = 1, r = segs[i]; // l 满足 r 不满足
    while(l+1<r){
      int mid = (l+r)/2;
      if(f(segs[i],mid) - f(segs[i],mid+1)>= x){
        l = mid;
      }else{
        r = mid;
      }
    }
    sum += f(segs[i],1) - f(segs[i],r);
    cnt += l;
  }
  return {cnt,sum};
}

int main(){
  ll cost = 0;
  scanf("%d",&n);
  rep(i,1,n+1){
    scanf("%lld",a+i);
    segs.push_back(a[i]-a[i-1]);
    cost += (a[i] - a[i-1])*(a[i] - a[i-1]);
  }
  scanf("%lld",&m);
  if(cost <= m){
    printf("0\n");
    return 0;
  }
  // 找的是 x 不是答案
  // l 满足 r 不满足
  ll l = 0, r = 1'000'000'000'000'000'000;
  while(l+1<r){
    // printf("[%lld %lld]\n",l,r);
    ll mid = (l+r)/2;
    if(calc(mid).second >= cost - m){
      l = mid;
    }else{
      r = mid;
    }
  }
  assert(l != 0);
  auto [c,s] = calc(r); // x+1 的所有
  printf("%lld\n",c + (cost - m - s)/l + !!((cost - m - s)%l));
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

bool p[100000010];
int ans = 0;
int a[30];
int n,k;

void dfs(int idx,int picked,int cnt){
  if(picked == k){
    ans+=!p[cnt];
    return ;
  }
  if(n - idx < k-picked)return ;
  dfs(idx+1,picked+1,cnt+a[idx]);
  dfs(idx+1,picked,cnt);
}

int main(){
  cin>>n>>k;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  p[1] = 1;
  rep(i,2,10001){
    if(p[i] == 1)continue;
    for(int j=i*i;j<100000001;j+=i){
      p[j] = 1;
    }
  }
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

//bool p[100000010];
int ans = 0;
int a[30];
int n,k;

bool pp(int v){
  if(v==1)return 1;
  int maxv = int(sqrt(v))+2;
  rep(i,2,maxv){
    if(v%i==0 && v!=i){
      return 1;
    }
  }
  return 0;
}

void dfs(int idx,int picked,int cnt){
  if(picked == k){
    // ans+=!p[cnt];
    ans+=!pp(cnt);
    return ;
  }
  if(n - idx < k-picked)return ;
  dfs(idx+1,picked+1,cnt+a[idx]);
  dfs(idx+1,picked,cnt);
}

int main(){
  cin>>n>>k;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  // p[1] = 1;
  // rep(i,2,10001){
  //   if(p[i] == 1)continue;
  //   for(int j=i*i;j<100000001;j+=i){
  //     p[j] = 1;
  //   }
  // }
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef uint64_t ull;
#define pb push_back
#define rep(i,a,n) for (ll i=a;i<n;i++)

ll quick_p(ll b, ll p,const ll mod){
  ll r = 1;
  while(p){
    if(p%2)(r*=b)%=mod;
    (b*=b)%=mod;
    p/=2;
  }
  return r%mod;
}

ll mr(ll base,ll v){
  if(base > v)return true;
  ll startp = v-1;
  while(startp%2 == 0)startp>>=1;
  ll p = startp;
  ll r = quick_p(base,p,v);
  while(p != v-1){
    if(r == v-1)return true;
    if(r == 1)return p == startp;
    p*=2;
    // overflow
    (r*=r)%=v;
  }
  return false;
}

bool is_prime_64(ll v){
  if(v < 2)return false;
  if(v < 4)return true;
  // %6 = 1 or 5
  if((v % 6) % 4 != 1)return false;
  ll test_g[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
  rep(i,0,7){
    if(!(mr(test_g[i],v)))return false;
  }
  return true;
}

int ans = 0;
int a[30];
int n,k;

void dfs(int idx,int picked,int cnt){
  if(picked == k){
    ans+=is_prime_64(cnt);
    return ;
  }
  if(n - idx < k-picked)return ;
  dfs(idx+1,picked+1,cnt+a[idx]);
  dfs(idx+1,picked,cnt);
}

int main(){
  cin>>n>>k;
  rep(i,0,n){
    scanf("%d",a+i);
  }
  dfs(0,0,0);
  cout<<ans<<endl;
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back

char s[200010];
int n,m;

void work(){
  scanf("%d %d",&n,&m);
  scanf("%s",s);
  int cnt1 = 0;
  rep(i,0,n){
    cnt1+=s[i] == '1';
  }
  if((cnt1 * m ) % n != 0){
    printf("-1\n");
    return ;
  }
  int x = (cnt1*m)/n;
  int c = 0;
  rep(i,0,m){
    c += s[i]=='1';
  }
  rep(i,0,n){
    if(c == x){
      if(i <= n-m){
        printf("1\n");
        printf("%d %d\n",i+1,i+m);
      }else{
        printf("2\n");
        printf("%d %d\n",1,m-(n-i));
        printf("%d %d\n",i+1,n);
      }
      return ;
    }
    c += s[(i+m)%n]=='1';
    c -= s[i]=='1';
  }
}

int main(){
  int t;
  cin>>t;
  while(t--)work();
  return 0;
}