# lss3.idiom - Idiom Number

Version: v2

2000ms / 262144 KB
Difficulty:1.0x

# Statement

This is supposed to be Problem A

Ookami is a werewolf girl. She loves learning foreign languages. One day, her Chinese teacher RedFish is talking about Chinese idioms. There are some Chinese idioms in a format, like "Piao Piao Yang Yang" is a "AABB"-type idiom.

Ookami is wondering whether numbers have this property too.

Formally, a format string is a string that contains upper-case letters. If we can replace each letter with a digit(0-9) so that the same letter is replaced by the same digit. We call this integer matches the format. The integer should not have leading zero.

For example, if the format is "AABCD" then "77512(A=7,B=5,C=1,D=2)" "77524(A=7,B=5,C=2,D=4)" "77777(A=B=C=D=7)" all match the format, while "12345" "78777" don't.

Given a format string and an integer K, find out the k-th smallest number that matches the format.

# Input

The string S and the integer K.

# Output

An integer. If the answer doesn't exist, print "ZJS!!"

# Example

[Input]
AABCD 6
[Output]
11005
[Explain]
The first 6:11000 11001 11002 11003 11004 11005

[Input]
ABAB 90
[Output]
9999

[Input]
AAAA 10
[Output]
ZJS!!
[Explain]
AAAA can match "1111" "2222" "3333" to "9999".


# Subtask

• For 50%, $1\leq |S|\leq 6,1\leq K\leq 10^6$

• For 100%, $1\leq |S|\leq 10^5,1\leq K\leq 10^{26}$