e-olymp
Задачі

Взлом хеш-функции

Взлом хеш-функции

В некоторых задачах защиты информации используются так называемые хеш-функции. Одним из важнейших классов хеш-функций являются так называемые полиномиальные хеш-функции.

Пусть дана строка S = s1s2...sl состоящая из цифр от 0 до 9. Тогда значение полиномиальной хеш-функцииp(S, x, m) вычисляется следующим образом

prb1797

(a mod b обозначает от деления числа a на число b). Например, пусть S = 0123, тогда p(S, 2, 5) = (0·1+1·2+2·4+3·8) mod 5 = 4.

Одним из способов применения хеш-функций является хранения паролей. Часто бывает так, что пароли приходится хранить в незащищённой таблице базы данных, поэтому вместо них хранят хеш-функции от них. При проверке пароля вычисляется хеш-функция от введённой строки и сравнивается со значением, хранящимся в таблице.

Ваша задача состоит в том, чтобы по заданным числам x, m, L и v найти строку S из цифр от 0 до 9 длины L, значение полиномиальной хеш-функции p(S, x, m) которой равно v.

Входные данные

Входной файл содержит четыре целых числа: x (x - простое число, 5x100), m (m является степенью двойки, 1m256), L (10L100) и v (0vm-1).

Выходные данные

В выходной файл выведите искомую строку или NO SOLUTION, если такой строки не существует.

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані
5 16 10 9
Вихідні дані
7432978180