A. Ургамал

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

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

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

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

Одойчууд дээш харах гурвалжин болох маш сонирхолтой ургамлыг суулгав. Энэ ургамал маш гайхалтай онцлогтой. Нэг жилийн дараа гурвалжин ургамал дөрвөн гурвалжин ургамалд хуваагддаг: тэдгээрийн гурав нь эцэг ургамалтайгаа адил чиглэлд харах ба нэг нь эсрэг зүгт чиглэсэн байна. Тэгээд жил болгон энэ үйл явц давтагддаг. Доорх зураг уг үйл явцыг харуулна.

% zurag

$n$ жилд хэдэн гурвалжин ургамлууд дээш харсан байхыг одойчуудад мэдэхэд туслаач.

Оролт

Эхний мөр ургамлын ургасан бүтэн жилүүдийн тоо болох $n (1 <= n <= 10^18)$ ганц бүхэл тоог агуулна.

C++ дээр 64-bit бүхэл тоог уншихдаа бүү %lld хэрэглэ. cin, cout урсгал эсвэл %I64d хэрэглэ.

Гаралт

$n$ жилийн турш хэдэн гурвалжин ургамал дээш харсан байх тоог $1000000007 (10^9 + 7)$-д хуваан үлдэгдэл нь болох ганц бүхэл тоог хэвлэнэ.

Орчуулсан: devman

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

Оролт
1
Гаралт
3
Оролт
2
Гаралт
10

Тэмдэглэл

Эхний жишээ тест зураг дээрх хоёр дугаар гурвалжинтай таарна, хоёр дугаар тест 3-р зурагтай таарна.

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