У Reziba есть много магических камней. Каждый магический камень может быть разделен на \(M\) обычных камней. Каждый магический (и обычный) камень занимает \(1\) единицу пространства. Обычный камень не может быть разделен.
Reziba хочет выбрать набор магических камней и разделить некоторые из них таким образом, чтобы общее пространство, занятое получившимся множеством, было равно \(N\). Если магический камень выбран и разделен, он занимает \(M\) единиц пространства (потому что это разделение на \(M\) камней); если же магический камень не разделен, то он занимает \(1\) единицу пространства.
Как много различных конфигураций получившихся множеств камней может иметь Reziba, если общее пространство, занятое этим множеством, равно \(N\)? Выведите ответ по модулю \(1000000007\) (\(10^9+7\)). Две конфигурации считаются различными, если количество магических камней, которые имеет Reziba, различается, или индексы камней, которые Reziba не разделяет, различаются.
Примечание
В первом тестовом примере каждый магический камень может быть разделен на \(2\) обычных камня, и мы знаем, что общее количество камней равно \(4\).
Пусть \(1\) обозначает магический камень, а \(0\) обозначает обычный камень.
Все конфигурации, которые вы можете иметь:
- \(1 1 1 1\) (никакие камни не разделены);
- \(0 0 1 1\) (первый магический камень разделен на \(2\) обычных камня);
- \(1 0 0 1\) (второй магический камень разделен на \(2\) обычных камня);
- \(1 1 0 0\) (третий магический камень разделен на \(2\) обычных камня);
- \(0 0 0 0\) (первый и второй магические камни разделены суммарно на \(4\) обычных камня).
Таким образом, ответ равен \(5\).