A. Олон өнгөт чулуу

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

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

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

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

Поликарпус улаан ба хөх чулуугаар тоглож байжээ. Тэр $n$ чулууг зүүнээс баруун тийш жагсаажээ. Нэг мэдэхэд чулуунууд зебройд хэлбэртэй болчихсон гэнэ.

Хэрвээ улаан, хөх чулуун дараалал нь ээлжилж байвал 'зебройд' гэж нэрлэдэг. Жишээ нь (улаан; цэнхэр; улаан) ба (цэнхэр) дараалал нь 'зебройд' бөгөөд (улаан, улаан) нь 'зебройд' биш.

Одоо Поликарпус дарааллаасаа хэдэн янзаар 'зебройд' дэд дараалал сонгож болохыг мэдмээр байгаа. Түүнд тусалж хариуг $1000000007$ ($10^9 + 7$)-д хуваахад гарах үлдлэгдлийг олно уу.

Оролт

Поликарпусын дараалалд байгаа чулууны тоо $n$ ($1 ≤ n ≤ 10^6$) өгөгдөнө.

Гаралт

Хариуг $1000000007$ ($10^9 + 7$)-д хуваахад гарах үлдлэгдлийг хэвлэ.

Орчуулсан: zoloogg

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

Оролт
3
Гаралт
6
Оролт
4
Гаралт
11

Тэмдэглэл

Let's consider the first test sample. Let's assume that Polycarpus initially had sequence (red; blue; red$), so there are six ways to pick a zebroid:

  • pick the first marble;
  • pick the second marble;
  • pick the third marble;
  • pick the first and second marbles;
  • pick the second and third marbles;
  • pick the first, second and third marbles.

It can be proven that if Polycarpus picks (blue; red; blue$) as the initial sequence, the number of ways won't change.

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