Мирко и Славко играют в игру. Мирко ходит первым и выбирает непустое множество пар чисел от 1 до N (включительно). При этом числа в одной паре должны быть различны и взаимнопросты. Например, для N = 5 , Мирко может выбрать такое множество пар: {(1, 2), (3, 4), (2, 5), (3, 5)}.

Славко ходит вторым и его задача - найти разделяющий элемент для множества пар Мирко. Разделяющим элементом для множества пар называется такое число x из диапазона [2: N ] , что для каждой пары ( a , b ) из множества выполняется одно из двух условий:

1. a , b < x

2. a , b ≥ x

Например, множество пар {(1, 2), (3, 4)} имеет разделяющий элемент x = 3 .

Если разделяющий элемент существует, Славко обязательно его найдет, и тогда он выиграет. Мирко же выиграет, если Славко не сможет найти разделяющий элемент. Он просит вас помочь: определите, как много множеств пар, удовлетворяющих условию, он может выбрать, чтобы гарантированно выиграть. Так как это число может быть очень большим, выведите его по модулю 1 000 000 000.

Одаренный предпринимательским талантом Мистер Картошечка открывает два новых магазина, где, как вы, вероятно, уже догадались, он будет продавать картошечку. Мистер Картошечка получает картошку от N фермеров. Каждый фермер предлагает ровно a _i картофелин с мешке общей стоимостью c _i . Мистер Картошечка собирается купить по мешку картошки у кадого из фермеров и распределить их в два своих магазина.

Обозначим среднюю цену картошки в магазинах за P ₁ и P ₂ . Средняя цена равняется отношению суммарной стоимости к количеству картошки в данном магазине. Мистер Картошечка хочет, чтобы значение P ₁ · P ₂ было минимальным.

Кроме того, хотя бы в одном магазине дожно быть ровно L мешков картошки.

Анике приснился необычный сон. В нем она увидели бесконечную доску. На той доске бесконечно много строк и бесконечно много столбцов, содержащих бесконечно много чисел. Что интересно, каждое число появляется на доске конечное число раз.

Оказывается, доска соответствует вполне понятным рекурсивным правилам. Первая клетка каждой строки содержит номер этой строки (начиная с 1). Значение же в каждой последующей клетке равно сумме значения в предыдущей клетке и перевернутого значения в предыдущей клетке. Перевернутое число можно получить, если записать в обратном порядке цифры десятичного представления числа.

Формально, если A ( i , j ) - значение в i -й строке и j -м столбце доски, то:

1. A ( i , 1) = i

2. A ( i , j ) = A ( i , j - 1) + rev ( A ( i , j - 1)) , если j > 1 .

rev ( x ) - операция разворота числа в его десятичном представлении. Например, rev (345) = 543 , а rev (1040) = 0401 = 401 .

Затем во сне Аника увидела дружелюбного призрака Бозо, появившегося из-за угла. Он сказал ей: "Аника! Если ты правильно ответишь на мои вопросы, я подарю тебе коробку вкусного печенья. А вопросы мои будут такие: я буду давать тебе по два числа A и B , а ты должна будешь сказать, сколько на доске чисел, лежащих в диапазоне [ A : B ] ".

Аника, хоть она и во сне, очень хочет поесть печенья, поэтому просит вас помочь ответить на вопросы Бозо.