암호 시도 횟수

유진이는 현수의 컴퓨터 암호를 찾으려고 한다. 먼저 암호에 사용할 수 있는 문자들을 순서대로 적어 두었다. 유진이는 이 순서를 기준으로 가능한 문자열을 길이 1부터 차례대로 시도한다. 같은 길이에서는 적어 둔 문자 순서가 사전순이 된다.

문자 집합이 bca라면 시도 순서는 b, c, a, bb, bc, ba, cb, cc, ca, ab, ac, aa, bbb, ... 와 같이 이어진다.

주어진 암호가 몇 번째 시도에서 나오는지 구하라.

첫 줄에 암호에 사용할 수 있는 문자들이 공백 없이 주어진다. 둘째 줄에 실제 암호가 주어진다.

사용할 수 있는 문자의 종류는 최대 100가지이며, 공백은 포함되지 않는다. 영문자는 대문자와 소문자를 서로 다른 문자로 취급한다. 암호 길이는 최대 1,000,000이다.

암호가 몇 번째 시도인지 출력한다. 값이 매우 클 수 있으므로 시도 횟수를 900528로 나눈 나머지를 출력한다.