At the International Language Olympiad the selection part is running. At this competition, everyone must represent his own language.

Murad decided that his language is interesting and participates in the selection. His language has m letters (c1, c2, ..., cm). Any word created from these letters exists in his language.

In order to make the language look more accurate, Murad decided to line up all his words in order. He arranged them in increasing order of lengths, and if the lengths of the words are the same, then in lexicographical order.

During the selection, all members of the jury liked Murad's language, and they decided to test it, giving Murad the task related to his language. Murad was given some word from his language and asked to find its order in the sequence of words that he has built.

Help Murad in this matter.

The answer can be very big, so find it modulo 280230412.

Input

First line contains the number of letters m (1 ≤ m ≤ 26) in Murad's language. Next line contains space separated letters in alphabetical order c1, c2, ..., cm. Third line contains word S (1 ≤ |S| ≤ 106) from Murad's language (here |S| denoted the length of the word S).

Output

Print the order of the word S in the constructed sequence of words, calculated modulo 280230412.

Explanation

In the first test the words in the language are: a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb,...

In the second test the words in the language are: a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa,...