Description

Given a positive integer $n$, please output the number of even entries in the first $n$ rows of Pascal's triangle modulo $1000003$.

Input Format

One line with a positive integer $n$.

Output Format

One line with an integer denoting the answer.

6

6

Hint

For $30\%$ of the testdata, $n \le 4 \times 10^3$.

For $70\%$ of the testdata, $n \le 4 \times 10^9$.

For $100\%$ of the testdata, $1 \le n \le 10^{15}$.

The first seven rows of Pascal's triangle:

       1
      1 1
     1 2 1
    1 3 3 1
   1 4 6 4 1
 1 5 10 10 5 1
1 6 15 20 15 6 1

Translated by ChatGPT 5