В Байтландии в ходу монеты n разных видов. Для удобства расчётов, достоинство монеты вида k обязательно делит достоинство монеты k + 1, а достоинство монеты вида 1 равно 1 тугрик. Отношение достоинств монет вида k + 1 и k равно ak. Также известно, что для любого x есть не более 20 видов монет, имеющих достоинство x.
У Байтазара с собой есть ровно bk монет вида k, и сейчас ему нужно заплатить ровно m тугриков. Также известно, что Байтазар не носит с собой более 3·105 монет. Байтазар хочет узнать, сколько у него есть способов заплатить m тугриков. Способы считаются различными, если для некоторого k в способах различается количество монет вида k. Как и всех в Байтландии, Байтазара количество способов интересует исключительно по модулю 109 + 7.
Выходные данные
В единственной строке выведите одно число — количество способов заплатить ровно m тугриков по модулю 109 + 7.
Примечание
В первом примере у Байтазара есть 4 монеты достоинства 1, и нужно заплатить 2 тугрика. Способ единственен.
Во втором примере у Байтазара есть по 4 монеты двух различных видов достоинства 1, и нужно заплатить 2 тугрика. Теперь способов 3: заплатить одну монету первого вида, одну — второго, заплатить две монеты первого вида, или заплатить две монеты второго вида.
В третьем примере достоинства монет равны 1, 3, 9.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
4
2
|
1
|
|
2
|
2
1
4 4
2
|
3
|
|
3
|
3
3 3
10 10 10
17
|
6
|