Задача Хитрий паліндром (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.