Задача Взлом хеш-функции

Описание

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

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

(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 - простое число, 5 ≤ x ≤ 100), m (m - является степенью двойки, 1 ≤ m ≤ 256), L (10 ≤ L ≤ 100) и v (0 ≤ v ≤ m − 1).

Формат выходных данных

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