Guest User

Untitled

a guest
Aug 29th, 2020
140
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. #define int long long
  4. #define pb push_back
  5. #define mp make_pair
  6. #define vi vector<int>
  7. #define vb vector<bool>
  8. #define pii pair<int,int>
  9. #define mii map<int,int>
  10. #define all(c)  c.begin(), c.end()
  11. #define rall(c) c.rbegin(), c.rend()
  12. #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  13. #define gcd(a,b) __gcd(a,b)
  14. #define lcm(a,b)  (x/gcd(x,y))*y
  15. #define inf (long long) 1e18
  16. #define neg_inf (long long) (-1*1e18)
  17. #define F first
  18. #define S second
  19. #define sz(x) ((int)(x).size())
  20. #define rep(i,n)  for(int i=0;i<n;i++)
  21. #define repd(i,n) for(int i=n-1;i>=0;i--)
  22. #define rep1(i,n) for(int i=1;i<=n;i++)
  23. #define deb(x) cout << #x << "=" << x <<"\n";
  24. const int N = 1e9 + 7;
  25.  
  26. int pow(int x, int y) { int res = 1; while (y > 0) { if (y & 1) res = ((res) * (x)); res %= N; y = y >> 1; x = ((x) * (x)); } return res; }
  27. int pow(int x, int y, int p)  {  int res = 1; x = x % p; while (y > 0) {if (y & 1) res = (res * x) % p; y = y >> 1; x = (x * x) % p;}   return res; }
  28.  
  29.  
  30. unsigned long long power(unsigned long long x,
  31.                          int y, int p)
  32. {
  33.     unsigned long long res = 1; // Initialize result
  34.  
  35.     x = x % p; // Update x if it is more than or
  36.  
  37.     while (y > 0) {
  38.         if (y & 1)
  39.             res = (res * x) % p;
  40.           y = y >> 1; // y = y/2
  41.         x = (x * x) % p;
  42.     }
  43.     return res;
  44. }
  45.  
  46. unsigned long long modInverse(unsigned long long n, int p)
  47. {
  48.     return power(n, p - 2, p);
  49. }
  50. unsigned long long nCrModPFermat(unsigned long long n,
  51.                                  int r, int p)
  52. {
  53.     if (r == 0)
  54.         return 1;
  55.     unsigned long long fac[n + 1];
  56.     fac[0] = 1;
  57.     for (int i = 1; i <= n; i++)
  58.         fac[i] = (fac[i - 1] * i) % p;
  59.  
  60.     return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
  61. }
  62.  
  63.  
  64. void solve()
  65. {
  66.     int n,m;
  67.     cin>>n>>m;
  68.     map<int,int> mm;
  69.     rep(i,n-1)
  70.     {
  71.         int a;
  72.         cin>>a;
  73.         mm[a]++;
  74.     }
  75.     mm[0]=1;
  76.     int srk=0;
  77.     if(sz(mm)==(*mm.rbegin()).F+1)
  78.     {
  79.         vector<int> kk;
  80.         for(auto x:mm)
  81.         {
  82.             kk.pb(x.S);
  83.         }
  84.         int ans=1;
  85.         for(int i=1;i<sz(kk);i++)
  86.         {
  87.             srk+=(kk[i]*(kk[i]-1))/2;
  88.             srk%=N;
  89.             ans*=pow(kk[i-1],kk[i],N);
  90.             ans%=N;
  91.         }
  92.  
  93.         if(srk>=(m-(n-1)))
  94.             ans*=nCrModPFermat(srk,m-(n-1),N);
  95.         else
  96.         {
  97.             cout<<0<<"\n";
  98.             return;
  99.         }
  100.         ans%=N;
  101.         cout<<ans<<"\n";
  102.     }
  103.     else
  104.     {
  105.         cout<<0<<"\n";
  106.     }
  107. }
  108.  
  109.  
  110.  
  111. int32_t main()
  112. {
  113.   // #ifndef ONLINE_JUDGE
  114.  //    freopen("gymnastics.in", "r", stdin);
  115.  //    freopen("gymnastics.out", "w", stdout);
  116.   // #endif
  117.     ios_base::sync_with_stdio(false);
  118.     cin.tie(NULL);
  119.     cout.tie(NULL);
  120.  
  121.     int t=1;
  122.     cin>>t;
  123.  
  124.    while(t--)
  125.    {
  126.       solve();
  127.    }
  128. }
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135. //code by-Roshan
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147. //unnecessary
  148. // bool cmp(pair<int,int> &a,pair<int,int> &b)
  149. // {
  150. //  if(a.F==b.F)
  151. //    return (a.S<b.S);
  152. //  else
  153. //    return (a.F<b.F);
  154. //  //< =chota wala pehle
  155. //  //> =chota wala baad me
  156. // }
  157.  
  158.  
  159. //better use this structure
  160. // struct s{
  161. //  int a;
  162. //  bool operator <(const s &x) const
  163. //  {
  164. //    return (a>x.a);
  165. //  }
  166. // };
  167.  
  168.  
  169.  
  170. //  priority_queue<int,vector<int>,greater<>> p;
  171. // (priority queue as min heap)
  172.  
  173.  
  174. //important to use this one
  175. // cout<<fixed<<setprecision(3)<<x<<" ";
  176.  
  177.  
RAW Paste Data