We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #215: Crack-free Walls

# Project Euler #215: Crack-free Walls

# Project Euler #215: Crack-free Walls

_{This problem is a programming version of Problem 215 from projecteuler.net}

Consider the problem of building a wall out of and bricks (horizontalĂ—vertical dimensions) such that, for extra strength, the gaps between horizontally-adjacent bricks never line up in consecutive layers, i.e. never form a "running crack".

For example, the following wall is not acceptable due to the running crack shown in red:

There are eight ways of forming a crack-free wall, written .

Calculate .

**Input Format**

The only line of each test file contains three integers separated by single spaces: , and .

**Constraints**

**Output Format**

Print exactly one integer that is .

**Sample Input 0**

```
9 3 1000
```

**Sample Output 0**

```
8
```