codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

70A.md (1756B)


      1 Source: https://codeforces.com/problemset/problem/70/A
      2 
      3 A. Cookies
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Fangy collects cookies. Once he decided to take a box and put cookies into it in some way. If we take a square *k* × *k* in size, divided into blocks 1 × 1 in size and paint there the main diagonal together with cells, which lie above it, then the painted area will be equal to the area occupied by one cookie *k* in size. Fangy also has a box with a square base 2*n* × 2*n*, divided into blocks 1 × 1 in size. In a box the cookies should not overlap, and they should not be turned over or rotated. See cookies of sizes 2 and 4 respectively on the figure:
     22 
     23  ![](https://espresso.codeforces.com/e2430045176f8e40706f40a1154690d9463d3792.png) 
     24 
     25 To stack the cookies the little walrus uses the following algorithm. He takes out of the repository the largest cookie which can fit in some place in the box and puts it there. Everything could be perfect but alas, in the repository the little walrus has infinitely many cookies of size 2 and larger, and there are no cookies of size 1, therefore, empty cells will remain in the box. Fangy wants to know how many empty cells will be left in the end.
     26 
     27 Input
     28 
     29 The first line contains a single integer *n* (0 ≤ *n* ≤ 1000).
     30 
     31 Output
     32 
     33 Print the single number, equal to the number of empty cells in the box. The answer should be printed modulo 106 + 3.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 9
     47 ```
     48 
     49 Note
     50 
     51 If the box possesses the base of 23 × 23 (as in the example), then the cookies will be put there in the following manner:
     52 
     53 ![](https://espresso.codeforces.com/1fe83a86be802a16c8f19d8ab81556d88104e40b.png)