АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1791. Лягушка на полигоне

Ограничение времени: 1 сек.
Ограничение памяти:262144 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

Лягушка прыгает по вершинам полигона (многоугольника), перемещаясь каждый раз в одну из двух соседних вершин. Определите, сколькими способами она может попасть из вершины 1 снова в вершину 1, сделав ровно K прыжков. Поскольку ответ может оказаться довольно большим, выведите его по модулю 109 + 7 (то есть остаток от деления на 109 + 7).

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

В единственной строке входных данных записаны через пробел два числа N и K – количество вершин многоугольника и количество прыжков лягушки (3 ≤ N 10001 ≤ K 106).

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

Выведите одно целое число – ответ.

Пример ввода

3 4

Пример вывода

6

 Система оценивания.

Подзадача 1 (30 баллов): N ≤ 1000, K ≤ 20

Подзадача 2 (30 баллов): N ≤ 1000, K ≤ 104

Подзадача 3 (40 баллов): N ≤ 1000, K ≤ 106

Во всех подзадачах баллы даются, только если все тесты этой подзадачи пройдены.


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Школьные олимпиады Вологодской области / II Областная олимпиада на приз губернатора 2017 / Заключительный этап, 9-10 класс /
1790. D - Выгодный бизнес 1791.
 
время генерации 0.079 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.