A. Жигнэмэг

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Панги жигнэмэг цуглуулдаг. Нэгэн өдөр тэрээр хайрцаг авч, жигнэмэгүүдээ түүн дотор ямар нэг байдлаар хийж байхаар шийдлээ. Хэрэв бид $k × k$ хэмжээтэй хайрцаг авбал $1 × 1$ дөрвөлжингүүд болгон хуваагаад, гол диагоналийг түүний дээр орших тасалгаатай хамт будаасанаар будагдсан хэсэг нь $k$ хэмжээтэй нэг жигнэмэгийн эзлэх талбайтай тэнцүү байна Панги $2^{n} × 2^{n}$ суурьтай өөр нэг хайрцагтай бөгөөд үүнийгээ $1 × 1$ хэмжээтэй дөрвөлжингүүдэд хуваасан. Хайрцган дахь жигнэмэгүүд бие бие дээр давхардахгүй, хөдөлгөөнгүй байх ёстой. Жигнэмэгүүд зурагт өгөгдсөний дагуу $2$, $4$ гэх мэт өөр өөр хэмжээтэй байна.

Жигнэмэгийг овоолохын тулд бяцхан далайн морьнууд дараах дүрмийг ашигладаг. Тэрээр хайрцганы аль нэг хэсэгт багтах хамгийн том жигнэмэгийг савнаас нь гаргаад хайрцганд хийнэ. Бүх зүйл төгс байж болох байсан ч харамсалтай нь бяцхан далайн морь $2$ болон түүнээс том хэмжээний /$1$ -ийн хэмжээтэй жигнэмэг байгаагүй/ хязгааргүй олон жигнэмэгтэй байсан ч хайрцганд хоосон зай байсаар байв. Панги хамгийн сүүлд хэдэн хоосон тасалгаа үлдэхийг мэдэхийг хүсч байна.

Оролт

Эхний мөр нь $n$ ($0 ≤ n ≤ 1000$) гэсэн цорын ганц бүхэл тоо агуулж байна.

Гаралт

Хайрцаг дахь хоосон тасалгааны тоо хэд байхыгол. Хариу $10^{6} + 3$ модультай гарна.

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
3
Гаралт
9

Тэмдэглэл

Хэрэв жишээнд өгөгдсөний дагуу хайрцагны суурь $2^{3} × 2^{3}$ бол жигнэмэгийг харйрцганд дараах байдлаар хийнэ.

Сэтгэгдлүүдийг ачааллаж байна...