The Barefooted Acrobatics People's Club wants to make a group photo in an original way. For the photo, they want to make a human pyramid, where each person rests on the ground or rests on the shoulders of two people below him or her.
Making a human pyramid demands a lot from the acrobats involved, so the club selected a group consisting of strong people of which they are assured that these people can carry enough weight. The others are 'agile' and to make sure everyone is comfortable during the photo, there can only be agile people directly above an agile person.
The photographer wants to make a photo of a pyramid with h people on the floor, h−1 on the second layer, h−2 on the third layer, and so on, with a single person on the hth layer. You have s strong people at your disposal, and the other 21h(h+1)−s people are agile. What is the number of ways you can arrange the pyramid satisfying the demands of the photographer? Since this number may be large, you should find it modulo 109+7.
Two pyramids P_1 and P_2 are different if there exists a location where P_1 has an agile person and P_2 a strong person, or vice versa.
The input consists of:
Output the number of possible ways to build a pyramid with the given constraints, modulo 109+7.