Processing math: 100%

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.)

Contributed by Kavish Lodha

Solved by 24 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.