B-sequence
Source: National Olympiad in Informatics, Romania 2005 (National Team Selection, 2nd day)
Authors: Tiberiu Danet and Silviu Ganceanu
Let N be a natural number, where 2 <= N <= 1018. We define a b-sequence of length N as a sequence x0, x1, ..., xN-1, where for any 0 <= i < N, we have
xi = 1, if i has an odd number of 1 bits in its binary representation
xi = 0, if i has an even number of 1 bits in its binary representation
For example, for N=7 we obtain the following b-sequence of length 7: 0110100, because:
| i (in base 10) | i (in base 2) | xi |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 10 | 1 |
| 3 | 11 | 0 |
| 4 | 100 | 1 |
| 5 | 101 | 0 |
| 6 | 110 | 0 |
Determine M, the number of palindromic subsequences of length at least 2 from a b-sequence of length N. (The sequence xi, xi+1, ..., xj-1,xj is palindromic if xi=xj, xi+1=xj-1, ...)
Input
The input file bsir.in contains on the first line the natural number N.
Output
The output file bsir.out will contain M modulo 30103 (the remainder of the division M / 30103).
Sample Input/Output
| bsir.in | bsir.out |
|---|---|
| 10 | 8 |
| bsir.in | bsir.out |
| 21 | 30 |