Злам хеш-функції
У деяких задачах захисту інформації використовуються так звані хеш-функції. Одним із найважливіших класів хеш-функцій є поліноміальні хеш-функції.
Нехай дано рядок S = s_1s_2...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, якщо такого рядка не існує.