Password Attempt Count

Eugene wants to find Hyun-su's computer password. He first writes down the usable characters in a fixed order. Using that order, he tries every possible string starting from length 1. Among strings of the same length, the written character order defines lexicographic order.

If the character set is bca, the trial order begins b, c, a, bb, bc, ba, cb, cc, ca, ab, ac, aa, bbb, ... .

Determine on which attempt the given password appears.

The first line contains the usable password characters with no spaces. The second line contains the actual password.

There are at most 100 kinds of usable characters, and spaces are not allowed. English letters are case-sensitive. The password length is at most 1,000,000.

Print the attempt number on which the password appears. Because the value can be very large, print the attempt number modulo 900528.