Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Beautiful String

By khepa98 · Limits 1s, 512 MB

Given 3 sets of strings A, B, C find how many numbers of beautiful strings can be created from these sets. All the strings are consisted of lower case English letters only.

A beautiful string is concatenation of 3 string p, q, r. Which means if x is a beautiful string then x = (p + q+ r).
Where p is from A, q is from B and r is from C.
And also lexvalue(q) > lexvalue(p) and lexvalue( r ) < lexvalue(q).

lexvalue of a string is demonstrated below with some examples

lexvalue("a") = 1, lexvalue("b") = 2, …, lexvalue("z") = 26, lexvalue("aa") = 27, lexvalue("ab") = 28, …, lexvalue("az") = 52, lexvalue("ba") = 53, lexvalue("bb") = 54, …, lexvalue("bz") = 78, …, lexvalue("za") = 677, lexvalue("zb") = 678, …, lexvalue("zz") = 702, lexvalue("aaa") = 703, lexvalue("aab") = 704, …, lexvalue("aaz") = 728, …, lexvalue("zzz") =18278, …

Input

First line contains 3 integers. Number of strings in set A, B, C respectively. In next 3 lines there will be 3 sets of space separated strings.

11 <= Number of strings in A, B, C <= 10510^{5}
For all strings, 11 <= lexvalue(string) <= 10510^{5}

Output

Print one integer, number of possible beautiful string modulo 999961.

Sample

InputOutput
3 3 2
aa av e
s ay t
r aas
5

Here in sample test case 5 beautiful string can be made.

For "s", we can make "esr" ( taking e from set A, s from set B and r from set C.

For "ay", we can make "aaayr" ( taking aa from set A, ay from set B and r from set C ) "avayr" and "eayr" accordingly.

For "t", we can make "etr".


    Discussion

    Statistics


    91% Solution Ratio

    YouKnowWhoEarliest, 6M ago

    FAHIM.ctgFastest, 0.0s

    cp_fanLightest, 1.3 MB

    YouKnowWhoShortest, 720B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.