У Геральда есть друг Поллард. Поллард увлекается счастливыми билетами. Причем, сначала он считал счастливым билет, между некоторыми цифрами номера которого можно поставить знаки действий и скобки так, чтобы результатом полученного арифметического выражения было число 100. Но он быстро исследовал такие билеты и перешел к более общему вопросу. Теперь он исследует k-счастливые билеты.

Поллард считает билет k-счастливым, если между, а так же слева и справа от цифр его номера можно поставить знаки арифметических действий (а именно, «+», «-», « × ») и скобки так, чтобы получилось корректное арифметическое выражение, значение которого равно k. К примеру, билет номер «224201016» является 1000-счастливым, поскольку ( - 2 - (2 + 4)) × (2 + 0) + 1016 = 1000.

Поллард настолько увлекся счастливыми билетами, что записался на семинар по счастливым билетам и, насколько известно Геральду, будет ежедневно ездить на него в один известный институт к семи вечера на одном и том же трамвайчике в течение m дней. В этом трамвайчике билеты имеют восьмизначные номера. И Геральд хочет сделать Полларду сюрприз — каждый день Поллард будет получать в трамвайчике k-счастливый билет. Кондуктор трамвайчика уже согласился выдавать Полларду все эти m дней определенные билеты, и хочет только, чтобы Геральд сказал ему, какие именно билеты нужно выдавать. В связи с этим, помогите Геральду подобрать ровно m различных k-счастливых билетов.