Password Attempt Count
Time limit2sMemory limit128 MB
Given a fixed alphabet order and a password, compute the attempt number at which that string appears in the length-then-lexicographic enumeration, modulo 900528.
- Level
Medium6 of 10
- Topics
- Math, String, Divide and conquer, Implementation
- Solved
- No attempts yet
Problem
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.
Input
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.
Output
Print the attempt number on which the password appears. Because the value can be very large, print the attempt number modulo 900528.