양의 정수 $N$이 주어진다.

$1 \le a, b < 2^N$을 만족하는 정수 쌍 $(a, b)$ 중에서 다음 조건을 만족하는 것의 개수를 $998244353$으로 나눈 나머지를 구하여라.

• 세 변의 길이가 $a, b, a \oplus b$인 비퇴화 삼각형(non-degenerate triangle)이 존재한다.

여기서 정수 $x, y$에 대하여 $x \oplus y$는 $x$와 $y$의 비트 단위 XOR 연산을 의미한다.

입력

첫 번째 줄에 정수 $N$이 주어진다. ($1 \le N \le 10^{18}$)

출력

조건을 만족하는 정수 쌍 $(a, b)$의 개수를 $998244353$으로 나눈 나머지를 출력한다.

예제

입력 1

2

출력 1

0

입력 2

5

출력 2

390

입력 3

10000

출력 3

851087540

참고

두 번째 예제에서, 예를 들어 $(a, b) = (13, 24)$는 조건을 만족한다. $a \oplus b = 13 \oplus 24 = 21$이므로, 세 변의 길이가 $13, 24, 21$인 비퇴화 삼각형이 존재한다.

조건을 만족하는 정수 쌍 $(a, b)$는 정확히 $390$개 존재한다.

음이 아닌 정수 $x, y$의 비트 단위 XOR $x \oplus y$는 다음과 같이 정의된다.

• $x \oplus y$의 이진 표현에서 $2^k$ ($k \ge 0$) 자릿수는 $x$와 $y$의 이진 표현에서 $2^k$ 자릿수 중 정확히 하나만 $1$일 때 $1$이고, 그렇지 않으면 $0$이다.

예를 들어, $3 \oplus 5 = 6$이다 (이진수로 표현하면 $011 \oplus 101 = 110$).