Задача Хитрый палиндром (pal333).

После выбора участка и разработки проектов строительства бассейна и фазенды Колыван получил смету на выполнение строительных работ. С учетом изменения курса доллара сумма получилась очень внушительной и Колыван, чтобы успокоиться, решил определить, является ли эта сумма палиндромом, т.е. таким числом, которое читается в обоих направлениях одинаково. Затем Колыван задался вопросом, а сколько существует способов получить палиндром из заданной последовательности цифр, удаляя из нее некоторое, возможно пустое, множество цифр. Наконец, он решил еще больше усложнить себе задачу и найти среди них все числовые палиндромы, которые делятся на число 333. Помогите ему решить эту задачу.

Формат ввода/вывода.  

Программа pal333 считывает с клавиатуры (стандартного устройства ввода) целое число N (1<=N<=100) – количество цифр числа. Затем считывается N цифр.

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

Пример входных и выходных данных.

Пояснение к примеру: из заданной последовательности цифр можно получить такие палиндромы, кратные 333: 0 (1-й ноль), 0 (2-й ноль), 00, 333 (1-я, 2-я и 3-я тройки), 333 (1-я, 2-я и 4-я тройки), 333 (1-я, 3-я и 4-я тройки), 333 (2-я, 3-я и 4-я тройки), 03330.