XOR-ABC

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

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

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

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

$R$의 $2$번째 비트는 $A$의 $2$번째 비트와 $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)$ 쌍의 개수를 $1\\,000\\,003$으로 나눴을 때 나머지를 출력한다. 단, $1\\,000\\,003$은 소수이다.