Problem #261
Occupying Houses
There are 65 houses arranged along a street and numbered from 0 to 64. Initially, only the 0^{th} and 64^{th} houses are occupied and the rest are empty. Then, one by one 63 buyers come to purchase the remaining houses. Each buyer can choose to occupy a house lying in the center of two consecutive occupied houses. In other words, if the a^{th} and b^{th} houses are occupied and no houses between them are occupied, then the buyer can occupy the (\frac{a+b}{2})^{th} house.
Calculate the number of ways all the remaining 63 houses can be occupied modulo 1000000007. Two ways are different if the order of occupying the houses is different in both ways. (Eg. the 2^{nd} person can either occupy the 16^{th} house or 48^{th} house, both of which are different ways.)