A. Разноцветные шарики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Поликарп играет с красными и синими шариками. Он выложил в ряд слева направо n шариков. Оказалось, что выложенные шарики образуют зеброид.

Непустая последовательность красных и синих шариков называется зеброидом, если цвета шариков в этой последовательности чередуются. Например, последовательности (красный; синий; красный) и (синий) — зеброиды, а последовательность (красный; красный) — нет.

Теперь Поликарпа заинтересовало, сколькими способами можно выбрать из этой последовательности подпоследовательность, которая также будет зеброидом? Помогите ему решить эту задачку, найдите остаток от деления количества способов на 1000000007 (109 + 7).

Входные данные

В первой строке записано единственное целое число n (1 ≤ n ≤ 106) — количество шариков в последовательности Поликарпа.

Выходные данные

Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).

Примеры
Входные данные
3
Выходные данные
6
Входные данные
4
Выходные данные
11
Примечание

Рассмотрим первый тестовый пример. Пусть изначально у Поликарпа была последовательность (красный; синий; красный), тогда выбрать зеброид можно шестью способами:

  • взять первый шарик;
  • взять второй шарик;
  • взять третий шарик;
  • взять первый и второй шарики;
  • взять второй и третий шарики;
  • взять первый, второй и третий шарики.

Можно доказать, что если в качестве изначальной последовательности Поликарпа взять (синий; красный; синий), то количество способов не изменится.