XOR-ABC

$\mathrm{xor}$ 연산은 두 수의 이진수 표현에서 각 자릿수를 비교해, 값이 같으면 $0$, 다르면 $1$을 계산한다.

다음은 $16$자리 이진수 $A=12$, $B=10$, $R = A$ $\mathrm{xor}$ $B$에 대한 예시이다.

$A$와 $B$가 모두 $16$자리 이진수이므로, $R$ 또한 $16$자리 이진수이다.

$R$의 $4$번째 비트는 $A$와 $B$의 $4$번째 비트가 모두 $1$로 같으므로 $0$이다.

$R$의 $2$번째 비트는 $A$와 $B$의 $2$번째 비트가 각각 $0$, $1$로 다르므로 $1$이다.

모든 자릿수에 대해 연산을 수행하면 $R$은 위와 같이 계산된다.

$K$자리 이진수 $A$, $B$, $C$에 대해 $1 \leq A < B < C \leq 2^K - 1$이고 $A$ $\mathrm{xor}$ $B = C$인 $(A,B,C)$ 쌍의 개수를 구하시오.

첫째 줄에 $K$가 주어진다. ($2 \leq K \leq 10^{18}$)

주어진 조건을 만족하는 $(A,B,C)$ 쌍의 개수를 $1000003$으로 나눈 나머지를 출력한다. $1000003$은 소수이다.