Задача Walk. На початку експерименту Робот стоїть спиною до глибокої ями на самому краєчку. Робот може робити один крок щосекунди або вперед, або назад, стояти під час експерименту на місці він не може. Підрахуйте, скількома способами робот може опинитися в ямі під час експерименту. (Опинитися в ямі означає опинитися хоча б на крок позаду від початкового положення робота)
Технічні умови. Програма Walk читає з пристрою стандартного введення єдине натуральне число – час експерименту t (0<t<=1000). Програма виводить на пристрій стандартного виведення шукану кількість способів по модулю 109+7
Приклад
Введення: 5
Виведення: 4
Коментар до прикладу: 4 «прогулянки» робота тривалістю не більшеніж 5 секунд закінчуються падінням у яму (правда, він на те й робот, щоб не розбитися і взяти участь в наступному експерименті…)
1.<-
2. -><- <-
3. -> -><- <- <-
4.-><- -><- <-