1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <string>
 6 #include <vector>
 7 #include <map>
 8 #include <set>
 9 #include <queue>
10 #include <sstream>
11 #include <algorithm>
12 using namespace std;
13 #define pb push_back
14 #define mp make_pair
15 #define mset(a, b)  memset((a), (b), sizeof(a))
16 typedef long long LL;
17 const int inf = 0x3f3f3f3f;
18 const int maxn = 1000000+10;
19 const int mod = 1000003;
20 LL a[maxn];
21 int main()
22 {
23     a[0] = 1;
24     for(int i=1;i<=maxn;i++)
25         a[i] = (a[i-1] * i * 2)%mod;
26     LL T;
27     cin  >> T;
28     while(T--){
29         LL n;
30         cin >> n;
31         if(n >= mod ){
32             cout << "0" << endl;
33             continue;
34         }
35         cout << a[n] << endl;
36     }
37     return 0;
38 }