Задача №1820. Лесники и лес
В одном секретном лесу росло несколько деревьев. Кроме того, в нём жило \(K\) лесников. Как известно, деревья — это круглые столбы положительной высоты и некоторого неотрицательного радиуса. Когда дерево рождается, оно имеет радиус 0 см и высоту 1 см. Каждый год 1 апреля каждый лесник выбирал некоторые деревья и поливал их. В другие дни никто из лесников деревья не поливал. Если в какой-то год дерево никто не поливал, то оно умирало. Заметим, что деревья могут иметь разный возраст. Если же его поливало \(x\) лесников, то у него вырастало годовое кольцо шириной \(x\) см, а его высота увеличивалась в \(x\) раз. Если в какой-то год радиус дерева становился ровно \(N\) см, то его срубали и везли на лесопилку. Если у дерева радиус становился больше \(N\) см, то оно умирало. Таким образом, на лесопилку приходили только деревья радиуса \(N\).
В один замечательный раз работники лесопилки заметили, что все деревья у них разные. Одинаковыми называются деревья, у которых одинаковое число годовых колец, кроме того, ширина внутреннего кольца одинаковая, ширины вторых колец одинаковые, и т. д. Т. е. ширины за одинаковые года у них одинаковые. Какой максимальной может быть сумма высот этих деревьев?
Так как ответ может быть большим, выведите его по модулю 1000000009.
В единственной строке входного файла содержится два натуральных числа — 1 \(\le\) \(K\) \(\le\) 100 и 1 \(\le\) \(N\) \(\le\) 1000000000.
Выведите единственное число — максимально возможную сумму высот деревьев по модулю 1000000009.
В первом примере всего на лесопилку могло попасть восемь различных деревьев радиуса 5 см:
* одно дерево высоты 1 см с пятью годовыми кольцами ширины 1 см каждое,
* четыре дерева высоты 2 см с тремя кольцами ширины 1 см и одним кольцом ширины 2 см и
* три дерева высоты 4 см с двумя кольцами ширины 2 см и одним кольцом ширины 1 см.
Суммарная высота этих деревьев равна 1+4*2+3*4=21.
Во втором примере единственное дерево радиуса 7, которое могло попасть на лесопилку, семь лет поливал всего один лесник. Высота этого дерева равна единице.
2 5
21
1 7
1