Олимпиадный тренинг

Задача . Пробежка по-простому


Задача

Темы:

Случалось ли у вас, что обед начался, а вы еще в корпусе? В таких ситуациях не остается ничего, кроме как, набрав воздуха в грудь, побежать.

Вы можете бежать только по тропинке. Будем считать, что Вы стоите на первом метре, а столовая находится на \(n\)-м метре. Так как тропинки в Звездном слишком узкие, чтобы по ним бегать, придумали особое правило: вы можете шагнуть на \(x\) метров, только если \(x\) — простое число. Вам очень повезло, ведь ваши Ваши ноги настолько длинные, что могут шагнуть на любое разрешенное расстояние. Неужели вам не интересно, сколькими способами можно дошагать до столовой?

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

Натуральное число \(n\) \((1 \le n \le 700)\) — метр, на котором стоит столовая.

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

Одно неотрицательное число — количество способов дошагать до столовой. Ответ необходимо вывести по модулю \(10^9 + 7\).

Примечание

Для n = 6:

  • 1 -> 3 -> 6 (прыжки на 2, 3)

  • 1 -> 4 -> 6 (прыжки на 3, 2)

  • 1 -> 6 (прыжок на 5)


Примеры
№Входные данныеВыходные данные
1
6
3
Статистика успешных решений по компиляторам
 Кол-во
Python1
С++1