Hide

Problem B
Chocolates

“My mom always said life was like a box of chocolates. You never know what you’re gonna get."

Forrest Gump is a young boy who goes to Greenbow County Central School. As a child, he enjoys running, dancing by swinging his hips, and eating chocolates. Most of all, he enjoys spending time with his best friend Jenny. However, Forrest isn’t the brightest boy by conventional means. While he fully embraces the life wisdom that his mama often imparts (such as through analogies with boxes of chocolates), he still has trouble keeping up with his classes.

Forrest’s math class is currently learning about shapes, specifically polygons. Forrest is falling behind because he doesn’t really understand what a polygon is. Jenny knows that if Forrest doesn’t keep up, his mama would have to take drastic measures to prevent the crooked principal, Mr. Hancock, from transferring Forrest to a special school. As such, Jenny has decided take Forrest’s schooling into her own hands.

Jenny has decided to use something that Forrest understands to explain polygons to him. She picks up a box of square chocolates and empties the pieces onto a napkin, leaving an empty box with $R$ rows and $C$ columns of empty cells. She places a single piece of chocolate in the box and says “With one chocolate here, I’ve made a square. A square is a polygon, Forrest."

\includegraphics[width=100pt]{chocolates1.png}

Jenny added two more chocolates around the first one and said, “We still have here a polygon, because we can trace a border around the chocolates without our fingers leaving the surface of the box."

\includegraphics[width=100pt]{chocolates2.png}

Jenny adds some more chocolates, filling up the entire box except a hole in the middle. “Now Forrest, no matter how we trace the outside box, there will always be a hole we can never draw unless our finger leaves the surface. So this here ain’t a polygon."

\includegraphics[width=100pt]{chocolates3.png}

Jenny removes a chocolate from the corner and says, “Now we’re back to a polygon again! As long as we can trace the border of our chocolates without crossing over where we already traced, we have ourselves here a polygon. As we trace, we can even have two corners barely touch, so long as we don’t overlap any border line we’ve already gone over.".

\includegraphics[width=100pt]{chocolates4.png}

That’s amazing Jenny. Even with just a small box like that, it seems like you can make so many of ’em", said Forrest.

That’s right Forrest!", said Jenny. “There’s so many ways to make a polygon using this box of chocolates, if I just made one at random and had you guess, you truly are never gonna know what you’re gonna get!"

Well, Jenny. Just how many ways do you think are there?" asked Forrest.

Hmm, I’m not quite sure about that Forrest." Jenny thought for a moment. "You really have me stumped."

Jenny wants to impress Forrest with the answer. Given the dimensions of the chocolate box, can you help her count the number of ways? For example, a $2$ by $2$ chocolate box has $13$ ways of forming a polygon:

   x.   .x   ..   ..   xx   x.   ..   .x   xx   .x   xx   x.   xx
   ..   ..   x.   .x   ..   x.   xx   .x   x.   xx   .x   xx   xx

Input

The first and only line of input consists of two space-separated integers $R$ and $C$ ($1 \leq R, C \leq 4$), specifying the dimensions of the box of chocolates.

Output

Print, on a single line, the number of different ways that chocolates can form a single polygon in the box. Note that if the same polygon can be placed at multiple different places in the box, then all of those ways are counted separately towards the answer.

Sample Input 1 Sample Output 1
1 2
3
Sample Input 2 Sample Output 2
2 2
13

Please log in to submit a solution to this problem

Log in