There are a lot of mountains in Chengdu, of course. But believe it or not, these mountains formed some beautiful skyline patterns.

For example, the skyline formed by some mountains shows below:

                    *
                   /\------------------ Height 6
    *         *   /  \  *
   /\--------/\--/    \/\-------------- Height 4
  /  \  *   /  \/     /  \  *
 /    \/\--/    \    /    \/\---------- Height 2
/     /  \/      \  /     /  \ 
------------------------------ Ground - Height 0

As you can see, all the summands of mountain is at "even" height. Actually, all the mountains in Chengdu have "even" height!

Now, the problem pops out to you: how many such skylines with length N in Chengdu?

You don't have to worry about the ways mountains ordered, take length N=6 for example,

 /\/\

/ /  \

its skyline is exactly the same as

 /\/\

/  \ \

Well, the answer may be as large as 2^N, so the only thing you need to output is the answer modulo 1000003.

A skyline is the shape of mountains' union, so it must both begin and end at height 0, and should never contain a flat land or somewhere underneath the ground.