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

Согласно многовековой традиции, сэр Петрейн каждую субботу ходит охотиться на дракона. Однако, за один вечер до выхода в очередной поход, он понял, что просто невозможно идти охотится на дракона без войска, состоящего из `n` верных воинов. Более того, чтобы охота получилась удачной, войско нужно разбить на три отряда, каждым из которых будет командовать опытный и закаленный в боях командир.

У Петрейна есть и необходимое количество воинов, и три командира, загвоздка только в том, что двое из них очень суеверны и будут лучше командовать отрядом, количество воинов в котором как-нибудь связано с их счастливым числом.

Счастливое число первого командира – `3`, поэтому количество воинов в первом отряде обязательно должно быть равно `3^k` для некоторого целого неотрицательного числа `k`. Второй командир хотел бы получить отряд, численность которого делится на `13`, даже если при этом в нем не будет воинов. Третий же согласен на любой отряд, однако из тактических соображений в нем должно быть никак не меньше `a` и не больше `b` воинов.

Обдумав все это, Петрейн понял, что существует несколько вариантов разбиений войска на нужные отряды. А вот посчитать точное количество таких разбиений он поручил Вам.

В первой строке входного файла содержится одно целое число `n` (`1\ ≤\ n\ ≤\ 10^9`) – количество рыцарей в войске. Во второй строке содержатся целые числа `a` и `b` (`1\ ≤\ a\ ≤\ b\ ≤\ n`), разделенные пробелом – ограничения на численность третьего отряда.

В выходной файл выведите одно целое число – количество возможных разбиений войска на отряды.

20
2 7

2

37
3 28

7