//#define DEBUG

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

const int MAXN = 2e5;
const int INF = 0x3f3f3f3f, MOD = 1000000007;
const long long LINF = LONG_LONG_MAX;
#define INIT(arr, val) fill(arr, arr+(int)(sizeof(arr)/sizeof(arr[0])), val)
#define REP(i, lb, rb, inc) for(int i = (lb); i < (rb); i += inc)
#define RREP(i, rb, lb, dec) for(int i = (rb)-1; i >= (lb); i -= dec)
typedef long long ll;
typedef queue<int> QI;
typedef vector<int> VI;
#define pb push_back
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
#define X real()
#define Y imag()
#define endl '\n'
#define dbg(a, b) cerr << "dbg: a " << b << endl;
#define dbg_itv(a, b, c) cerr << "dbg_itv: " << a << " " << b << " : " << c << endl
#define IOS() cin.tie(0); cout.sync_with_stdio(0); cout.tie(0)

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("O3")

PII ext_gcd(int a, int b) {
	if (b == 0) return {1, 0};
	else {
		int k = a/b;
		PII xy = ext_gcd(b, a%b);
		return {xy.S, xy.F - k*xy.S};
	}
}

signed main() {
	IOS();
	
	int t;
	cin >> t;
	while(t--) {
		ll n, s, k;
		cin >> n >> s >> k;
		ll g = __gcd(n, __gcd(s, k));
		n /= g, s /= g, k /= g;
		if (s % __gcd(k, n) != 0) {
			cout << "-1\n";
			continue;
		}
		ll x = ext_gcd(k, n).F;
		if (x < 0) x += n;
		cout << (x*(n-s))%n << endl;
	}
	
	#ifdef DEBUG
	cerr << "\nDebug Info:\n--------------------------------\n";
	#endif
}
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
#define PIL pair<int,LL>
#define PLI pair<LL,int>
#define PIII pair<int,PII>
#define PLL pair<LL,LL>
#define PLII pair<LL,PII>
#define VI vector<int>
#define VVI vector<VI>
#define VL vector<LL>
#define VVL vector<VL>
#define VPII vector<PII>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
#define sqr(x) ((x) * (x))
#define all(x) x.begin(),x.end()
#define watch(x) cout<<(#x)<<" = "<<(x)<<'\n'
#define mset(a,v) memset(a,v,sizeof(a))
#define setp(x) cout<<fixed<<setprecision(x)
#define EPS 0.00000000001
#define PI acos(-1)
#define loop(i,b,n) for(int i=b;i<n;++i)
#define rev_loop(i,b,n) for(int i=b;i>=n;--i)
using namespace std;

const int MOD = 1e9 + 7;
const LL MX = 1e9;
const LL INF = 1e9;

int main()
{
    //ofstream out("output.txt");
    //ifstream in("input.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    int a;
    set<int> st;

    loop(i,0,n)
    {
        cin>>a;
        st.insert(a);
    }

    LL ans = 1, p = 0;
    for(int x : st)
    {
        ans = (ans * (x - p + 1)) % MOD;
        p = x;
    }

    cout<<ans<<'\n';

    return 0;
}
