JOIN

 Problem Statement

Problem Statement for UnknownTree

### Problem Statement

You are given three int[]s: distancesA, distancesB, and distancesC. Each of these int[]s has exactly N elements.

We are interested in trees that satisfy the following conditions:
• The tree has exactly N + 3 vertices.
• Each vertex has a different label. The set of all labels is { A, B, C, 0, 1, ..., N-1 }.
• Each edge of the tree has a positive integer length.
• For each i (0 <= i < N), the distance between the vertex A and the vertex i is distancesA[i].
• For each i (0 <= i < N), the distance between the vertex B and the vertex i is distancesB[i].
• For each i (0 <= i < N), the distance between the vertex C and the vertex i is distancesC[i].

Find the number of trees that satisfy all of the conditions above, and return the number modulo 1,000,000,009.

### Definition

 Class: UnknownTree Method: getCount Parameters: int[], int[], int[] Returns: int Method signature: int getCount(int[] distancesA, int[] distancesB, int[] distancesC) (be sure your method is public)

### Notes

-The distance between two vertices s and t is defined as the sum of lengths of all edges on the only simple path between s and t.
-Two trees T1 and T2 are different when T1 has an edge u-v such that in T2 the edge u-v is either not present at all, or it has a different length than the edge u-v in T1.

### Constraints

-distancesA, distancesB, and distancesC will contain the same number of elements.
-distancesA, distancesB, and distancesC will contain between 1 and 50 elements, inclusive.
-Each element of distancesA, distancesB, and distancesC will be between 1 and 100,000,000, inclusive.

### Examples

0)

 `{1}` `{2}` `{3}`
`Returns: 6`
1)

 `{1, 2}` `{1, 2}` `{1, 2}`
`Returns: 1`
2)

 `{5, 4}` `{3, 2}` `{2, 1}`
`Returns: 8`
3)

 `{2, 4, 2}` `{1, 3, 3}` `{4, 6, 4}`
`Returns: 2`
4)

 `{4, 6, 1, 5, 3, 2, 5}` `{4, 2, 3, 1, 3, 2, 1}` `{5, 7, 2, 6, 4, 3, 6}`
`Returns: 12`
5)

 `{6, 4, 5, 6, 8, 1, 5, 6, 4, 2}` `{4, 2, 3, 4, 6, 1, 3, 4, 2, 2}` `{6, 4, 5, 6, 8, 3, 5, 6, 4, 4}`
`Returns: 9000`
6)

 `{8, 5, 6, 8, 6, 5, 6, 10, 8, 5, 10, 8, 7, 9, 7, 1, 11, 5, 9, 6, 6, 1, 6, 9, 8, 4, 12, 7, 5, 7, 6, 8, 12, 8, 6, 6, 5, 8, 5, 3, 3, 4, 8, 6, 6, 8, 8, 9, 7, 5}` `{9, 6, 7, 9, 7, 6, 7, 11, 9, 6, 11, 9, 8, 10, 8, 2, 12, 6, 10, 7, 7, 4, 7, 10, 9, 5, 13, 8, 6, 8, 7, 9, 13, 9, 7, 7, 6, 9, 6, 4, 4, 5, 9, 7, 7, 9, 9, 10, 8, 6}` `{8, 9, 6, 8, 2, 5, 6, 10, 8, 5, 10, 8, 7, 9, 1, 5, 11, 5, 9, 6, 6, 7, 6, 9, 8, 4, 12, 7, 5, 7, 6, 8, 12, 8, 6, 6, 5, 8, 1, 7, 3, 4, 8, 6, 6, 8, 8, 3, 7, 5}`
`Returns: 770724166`
7)

 ```{33030780, 30296205, 16842859, 28857842, 37928939, 27190807, 48689043, 33328845, 24254103, 3962046, 31043603, 25699520, 11297547, 27045586, 31603483, 23207518, 44089781, 48470539, 52366295, 39786470, 45623279, 21593844, 38639305, 27260993, 43899542, 36162768, 21640232, 43580853, 33826577, 30501815, 51470990, 2157904, 27823597, 9550575, 39234641, 24163007, 34155133, 42504989, 35821444, 36054200, 29026389, 29716374, 41764139, 19392309, 44258194, 19987908, 56722905, 46771885, 32668277, 40665175}``` ```{16191697, 13457122, 3776, 12018759, 21089856, 10351724, 31849960, 16489762, 7415020, 12877037, 14204520, 8860437, 9035480, 10206503, 14764400, 6368435, 27250698, 31631456, 35527212, 22947387, 28784196, 4754761, 21800222, 10421910, 27060459, 19323685, 4801149, 26741770, 16987494, 13662732, 34631907, 18996987, 10984514, 7288508, 22395558, 7323924, 17316050, 25665906, 18982361, 19215117, 12187306, 12877291, 24925056, 2553226, 27419111, 3148825, 39883822, 29932802, 15829194, 23826092}``` ```{19337227, 16602652, 3149306, 15164289, 24235386, 13497254, 34995490, 19635292, 10560550, 16030119, 17350050, 12005967, 12188562, 13352033, 17909930, 3215353, 30396228, 34776986, 38672742, 26092917, 31929726, 7907843, 24945752, 13567440, 30205989, 22469215, 7946679, 29887300, 20133024, 16808262, 37777437, 22150069, 14130044, 10441590, 25541088, 10469454, 20461580, 28811436, 22127891, 22360647, 15332836, 16022821, 28070586, 5706308, 30564641, 6294355, 43029352, 33078332, 18974724, 26971622}```
`Returns: 101733071`

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
Single Round Match 565 Round 1 - Division I, Level Three