E. Гурвалжин

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

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

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

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

Өнгөрсөн зуныг Петр эмээгийндээ өнгөрөөв. Эмээгийнх нь хоттой хонь руу зэргэлдээх ойгоос чоно дайрдаг гэж дуулснаас хойш тэрээр ой дундуур явах, ойг тойрох, түүнчлэн гэрээсээ гарахаас ч айдаг болчихсон. Түүний хэлж буйгаар бол энэ нь чононоос айсан хэрэг биш бөгөөд харин түүний бодлоор $n$ шатлалтай ойн хачин хээнээс болсон гэж байлаа. Энд $n$ нь тэгш тоо юм.

Орон нутгийн зөвлөлөөс танд тус бүс нутгийн газрын зураг өгсөн. Уг зурагт эмээгийн байшинг $H$ цэгээр, ойн шигүү хэсгийг саарлаар тэмдэглэжээ (зураг харна уу).

Удаан хугацаагаар гэртээ байсны эцэст Петр эмээгийнхээ ятгалганд орж, цэвэр агаар амьсгалахаар гарахаар шийджээ. Болгоомжтой байхын тулд Петр маршрутаа урьдчилан бэлдэв. Петрийн хамгийн тохиромжтой хэмээж буй маршрут нь дараах хэв шинжүүдтэй байна:

  • эмээгийн байшингаас эхлэж, буцаад тэндээ очиж төгсөнө;
  • маршрут нь зөвхөн ойн замаар дайрна (зураг дээр хараар тэмдэглэгдсэн хэрчмүүд);
  • маршрут нь эерэг урттай байна (цэвэр агаар амьсгалахын тулд Питер тодорхой зайнд алхах хэрэгтэй);
  • маршрут нь өөрийгөө хөндлөн огтолж болохгүй;
  • энэ маршрутанд ойн шигүү хэсгийг дайрсан ямар ч хэсэг байх ёсгүй;

Петрийн явахад хамгийн тохиромжтой гэж бодож буй маршрут нийтдээ хэд байж болох вэ? Энэ тоог $1000000009$-д хуваасан үлдэгдлийг олно уу.

Зурагт $n=12$ бүсийн газрын зураг жишээ болгон өгөгджээ. Газрын зураг нь энгийн бүтэцтэй учир та энэ жишээг ашиглан бусад $n$-ий хувьд төстэйгээр маршрут байгуулж болно.

Оролт

Оролтын мөр нь тэгш $n$ ($2≤n≤10^{6}$) бүхэл тоог агуулна.

Гаралт

Петрийн аялах боломжтой маршрутын тоог $1000000009$-д хуваасан үлдэгдлийг хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
2
Гаралт
10
Оролт
4
Гаралт
74
Сэтгэгдлүүдийг ачааллаж байна...