# Villages and Bridges

**Discrete Mathematics**Level pending

Several small villages are situated on the banks of a straight river. On one side, there are 20 villages in a row and on the other there are 15 in a row. We would like to build bridges, each of which connects a village on the one side with a village on the other side. The bridges must be straight, must not cross and it should be possible to get from any village to any other village using only those bridges ( and not by any roads that might exist between villages on the same side of the river). How many different ways are there to build the bridges?

The answer to this question is very large, so don't get afraid on seeing it. for you to be sure i can give you a hint for the answer. its a 9 digit number starting with 8 and ending with two zeros.