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