P1762 Even Numbers

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

One line with a positive integer $n$.

One line with an integer denoting the answer.

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: ```plain 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