Задача J. Возведение числа в большую степень ≡

Условие

Пусть имеются два длинных целых числа A и B, записанные в десятичной системе счисления.

Требуется возвести A в степень B, взяв остаток от деления по модулю P, представленному в виде произведения взаимно простых чисел: P = p₁ ⋅ p₂ ⋅ …  ⋅ p_k.

Полученный результат следует вывести в десятичной системе счисления.

Формат входного файла

Первые две строки входного файла "input.txt" содержат числа A и B.
Далее указано число k, за которым следует ровно k значений p_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать полученный результат, представленный в десятичной системе счисления.

Ограничения

2 ≤ (A, B) ≤ 10²⁰⁰⁰,

2 ≤ p_i ≤ 10⁹, НОД(p_i, p_j) = 1, ∀ i ≠ j,

1 ≤ k ≤ 10³

Примеры тестов

1234567890
101201230123401234501234560123456701234567801234567890

10
13 47 337501 37 1806000 19 29 11209 79 11013109

48424710506557820285677213386000

30
20

10
13 47 337501 37 1806000 19 29 11209 79 11013109

348678440100000000000000000000