VK Cup 2012 Финал, пробный тур |
---|
Закончено |
Поликарп играет с красными и синими шариками. Он выложил в ряд слева направо n шариков. Оказалось, что выложенные шарики образуют зеброид.
Непустая последовательность красных и синих шариков называется зеброидом, если цвета шариков в этой последовательности чередуются. Например, последовательности (красный; синий; красный) и (синий) — зеброиды, а последовательность (красный; красный) — нет.
Теперь Поликарпа заинтересовало, сколькими способами можно выбрать из этой последовательности подпоследовательность, которая также будет зеброидом? Помогите ему решить эту задачку, найдите остаток от деления количества способов на 1000000007 (109 + 7).
В первой строке записано единственное целое число n (1 ≤ n ≤ 106) — количество шариков в последовательности Поликарпа.
Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).
3
6
4
11
Рассмотрим первый тестовый пример. Пусть изначально у Поликарпа была последовательность (красный; синий; красный), тогда выбрать зеброид можно шестью способами:
Можно доказать, что если в качестве изначальной последовательности Поликарпа взять (синий; красный; синий), то количество способов не изменится.
Название |
---|