ABABABAB X76690


Statement
 

pdf   zip

html

Consider the following formula:

A + B * A + B * A + B * A + B 

We can obtain many different values by replacing each A with an arbitrary number from set A, and each B with an arbitrary number from set B.

Even more, in this problem we are allowed to place parentheses in any way we want. For example, (A+B)*(A+B)*(A+B)*(A+B) can be a very big number. We don’t like very big numbers.

Output the number of ways we can obtain a result which is at most M.

Input

The first line of input contains four numbers: N, M, QA, QB. We have 1 ≤ N ≤ 16, 1 ≤ M ≤ 1000, 1 ≤ QA, QB ≤ 1000. N is the number of operands (8 in the formula above, it always starts with A).

The second line contains QA non-negative integers — these are the elements of A. Each of them is different, and in range from 0 to 10000.

The third line contains QB non-negative integers — these are the elements of B. Each of them is different, and in range from 0 to 10000.

Output

Output the number of ways of obtaining at most M, modulo 1000003.

Public test cases

  • Input

    8 1000 1 1
1
1

    Output

    429

  • Input

    8 1000 2 2
1 2
1 2

    Output

    109824

  • Input

    2 1000 3 3
400 500 600
400 500 600

    Output

    6
    • Information
    Author
    Eryk Kopczynski
    Language
    English
    Official solutions
    Unknown. This problem is being checked.
    User solutions
    C++