Задача Хитрый палиндром (pal333).
После выбора участка и разработки проектов строительства бассейна и фазенды Колыван получил смету на выполнение строительных работ. С учетом изменения курса доллара сумма получилась очень внушительной и Колыван, чтобы успокоиться, решил определить, является ли эта сумма палиндромом, т.е. таким числом, которое читается в обоих направлениях одинаково. Затем Колыван задался вопросом, а сколько существует способов получить палиндром из заданной последовательности цифр, удаляя из нее некоторое, возможно пустое, множество цифр. Наконец, он решил еще больше усложнить себе задачу и найти среди них все числовые палиндромы, которые делятся на число 333. Помогите ему решить эту задачу.
Формат ввода/вывода.
Программа pal333 считывает с клавиатуры (стандартного устройства ввода) целое число N (1<=N<=100) – количество цифр числа. Затем считывается N цифр.
Программа pal333 выводит на экран (стандартное устройство вывода) единственное число – количество способов получения чисел-палиндромов, делящихся на число 333, из заданной последовательности цифр. Ответ должен быть выведен по модулю 10007. Палиндром может начинаться с ведущих нулей.
Пример входных и выходных данных.
|
Ввод |
Вывод |
|
6 303330 |
8 |
Пояснение к примеру: из заданной последовательности цифр можно получить такие палиндромы, кратные 333: 0 (1-й ноль), 0 (2-й ноль), 00, 333 (1-я, 2-я и 3-я тройки), 333 (1-я, 2-я и 4-я тройки), 333 (1-я, 3-я и 4-я тройки), 333 (2-я, 3-я и 4-я тройки), 03330.