A huge aerolite had fallen in Antarctica!!!Many disasters happened and lots of people lost their lives, homes or even everything.Blue Mary, the well-known scientist, is to work out the secret of this aerolite for further study.

Blue Mary has found out that their are some numbers on this aerolite, 5 per line:

1 1 1 1 6
0 0 6 3 57
8 0 11 3 2845

With her genius, Blue Mary knows that the 5th number is the key to solve the problem, but in some lines the 5th numbers were destoryed and we cannot know what they are instantly.

After some days, she finds out the way to calculate the 5th number finally, which is:

For example "()(())[]", "{()[()]}", "{{[[(())]]}}"(all without quotes) are REs and "()([])()","[()" are not REs.

The deep of an RE A, D(A), is defined as below:

Such as D("(){()}[]")=2.

Suppose the first 4 numbers in current line are L1,L2,L3 and D, then the 5th number in current line is the number of REs modudo 11380.Each of the REs must have a depth of D and is made of L1 {}, L2 [] and L3 ().

Now Mary needs your help to work out the 5th number.

Input

Input contains exactly 10 test cases.Each test case contains one line, which contains 4 numbers L1,L2,L3,D(0<=L1,L2,L3<=10, 0<=D<=30), separated by single spaces.

Output

Ten lines, each contains a single integer denoted the 5th number.

Example

Input:
1 1 1 1
0 0 6 3
1 1 1 2
[and 7 test cases more]

Output:
6
57
8
[and 7 test cases more]