Could someone help me with the possible solution for the following question.

It is from a contest that ended today.

problem name:- BEAUTIFUL STONES 1

problem link:- https://www.hackerrank.com/contests/execute--19-1/challenges/beautiful-stones-1

problem:-

You have two different types of stones. Your task is to find the total number of different patterns that can be formed such that stone of same type appear in a blocks of odd length.

**Input Format**

The first line contains an integer T, representing the number of test cases.

Each of next T line contains an integer N, denoting the length of pattern

**Note** There are infinite supply of each stone

It is gaurenteed that N is even.

**Constraints**

1<=T<=100000

1<=N<=10^18

**Output Format**

For each test case print the total number of ways modulo 10^6+3 in a new line.

**Sample Input 0**

1 4

**Sample Output 0**

6

**Explanation 0**

6 Different ways are:

stone1 stone1 stone1 stone2

stone2 stone1 stone1 stone1

stone2 stone2 stone2 stone1

stone1 stone2 stone2 stone2

stone1 stone2 stone1 stone2

stone2 stone1 stone2 stone1

Ps:Thanks in advance