A. 知识拼图

熊妈妈总是制作边长为2^n的知识饼干，熊孩子总是沿着对角线吃（对角线不会被吃掉），例如n=1,n=2时：

熊妈妈对此非常不满，于是她从熊孩子剩下的无数块饼干中挑选一些，制作新的饼干：例如n=3时：

她拿一块n=3的，然后拼接一块n=2的，然后拼接n=1的。因为她从来不做n=0的即边长为1的饼干，所以熊孩子也就不会剩下这样的饼干。

现在，熊妈妈想知道利用熊孩子剩下的饼干制作一个边长为2^n的饼干需要填补多少个边长1×1的部分，才能使饼干上没有空白部分。

一行，一个整数，表示n。

对于100%的数据：

1\le n \le 10^8。

一行，一个整数，表示需要填补的空白的个数对10^6+3取模的结果。