24731번 - 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円$은 소수이다.

제한

서브태스크

힌트