cuburi
Johnie likes to play using building blocks. He has an infinite number of white blocks (with all six facets white) and black (with all six facets black). All his blocks have the width, height and length of one meter.
In order to build a building, Johnie places the cubes on N levels, each level containing 2*2 blocks. So in the end Johnie obtains a building of height N, width 2 and length 2. After he got tired of building random buildings, Johnie realized that a building is all the more beautiful if there is a connected component made only of white blocks, which contains at least K elements.
We say that two blocks, X and Y, are in the same connected component if:
• X and Y are placed in adjacent positions in the building (they have a common "facet");
• X is adjacent to a block Z, and Z is in the same connected make-up with Y.
Task
Determine the number of beautiful buildings that can be built. The result must be displayed modulo 10000.
Input Data
Input file cuburi.in contains on the first line two positive integers, N and K, separated by a blank, with the meaning from the task description.
Output Data
Output file cuburi.out will contain a single line with the number of beautiful buildings that can be built, modulo 10000.
Constraints and Mentions
• 1 <= N <= 40
• 1 <= K <= 4*N
Example
| cuburi.in | cuburi.out | Explanations |
|
3 12 |
1 |
There is a single building, with all white blocks. |
| cuburi.in | cuburi.out | Explanations |
|
4 15 |
17 |
There are 17 buildings, because all the blocks that have 15 white and one black blocks are valid (16 blocks of this kind) as well as the building that has all blocks white. |
| cuburi.in | cuburi.out |
| 6 15 | 2244 |
Time limit: 0.6 seconds/test
Daniel Pasaila
"Al. I Cuza" University, Iaşi
IT Department
danielpasaila@yahoo.com