Counting Even Numbers in Pascal's Triangle

Given a positive integer n, output the sum of even numbers in the first n rows of Pascal's (Yang Hui's) Triangle modulo 1000003.

The Pascal's Triangle is defined such that the i-th row (0-indexed) has i+1 numbers. It is known that the number of odd numbers in the i-th row is given by \(2^{\mathrm{popcount}(i)}\), where \(\mathrm{popcount}(i)\) is the number of 1's in the binary representation of i. Therefore, the number of even numbers in the i-th row can be computed as:

[ \text{even_count}(i) = (i+1) - 2^{\mathrm{popcount}(i)} ]

Your task is to compute the sum of \(\text{even_count}(i)\) for all rows i from 0 to n-1 and output the result modulo \(1000003\).

inputFormat

The input consists of a single positive integer n (1 ≤ n).

Format: A single line containing the integer n.

outputFormat

Output a single integer representing the total number of even numbers in the first n rows of Pascal's Triangle, taken modulo 1000003.

Format: A single integer.

sample

1

0