Summation of Modified Binomial Coefficients

Given an integer n, define the function
\( F(x) = ((x+1) \bmod 3) - 1 \), which evaluates as follows:

• If \( x \equiv 0 \pmod{3} \), then \( F(x)=0 \).
• If \( x \equiv 1 \pmod{3} \), then \( F(x)=1 \).
• If \( x \equiv 2 \pmod{3} \), then \( F(x)=-1 \).

Let \( C(r, l) \) be the binomial coefficient defined by

\[ C(r, l)=\frac{r!}{l!(r-l)!},\]

for \( 0 \leq l \leq r \leq n \). The task is to compute the following sum modulo \( 1732073999 \):

\[ S = \sum_{l=0}^{n} \sum_{r=l}^{n} F\bigl(C(r, l)\bigr) \pmod{1732073999}.\]

Hint: Note that since \( F(x) \) depends only on \( x \bmod 3 \), and Lucas' Theorem applies to binomial coefficients modulo a prime, it can be shown that:

[ \sum_{l=0}^{r} F\bigl(C(r, l)\bigr) = 2^{c_1(r)},]

where \( c_1(r) \) is the number of digits equal to 1 when \( r \) is represented in base 3. Hence, the overall sum becomes

[ S = \sum_{r=0}^{n} 2^{c_1(r)} \pmod{1732073999}.]

Your task is to compute \( S \) given \( n \).

inputFormat

The input consists of a single integer n (\(0 \le n \le 10^{18}\)).

outputFormat

Output a single integer representing the value of \( S \) modulo \( 1732073999 \).

sample

0

1