print2162. Разбиение войска

printРазбиение войска

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Согласно многовековой традиции, сэр Петрейн каждую субботу ходит охотиться на дракона. Однако, за один вечер до выхода в очередной поход, он понял, что просто невозможно идти охотится на дракона без войска, состоящего из `n` верных воинов. Более того, чтобы охота получилась удачной, войско нужно разбить на три отряда, каждым из которых будет командовать опытный и закаленный в боях командир.
У Петрейна есть и необходимое количество воинов, и три командира, загвоздка только в том, что двое из них очень суеверны и будут лучше командовать отрядом, количество воинов в котором как-нибудь связано с их счастливым числом.
Счастливое число первого командира – `3`, поэтому количество воинов в первом отряде обязательно должно быть равно `3^k` для некоторого целого неотрицательного числа `k`. Второй командир хотел бы получить отряд, численность которого делится на `13`, даже если при этом в нем не будет воинов. Третий же согласен на любой отряд, однако из тактических соображений в нем должно быть никак не меньше `a` и не больше `b` воинов.
Обдумав все это, Петрейн понял, что существует несколько вариантов разбиений войска на нужные отряды. А вот посчитать точное количество таких разбиений он поручил Вам.
В первой строке входного файла содержится одно целое число `n` (`1\ ≤\ n\ ≤\ 10^9`) – количество рыцарей в войске. Во второй строке содержатся целые числа `a` и `b` (`1\ ≤\ a\ ≤\ b\ ≤\ n`), разделенные пробелом – ограничения на численность третьего отряда.
В выходной файл выведите одно целое число – количество возможных разбиений войска на отряды.

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

20
2 7

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

2

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

37
3 28

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

7
Источник: neerc.ifmo.ru/school
loading