Count the ways to fold a strip of N segments so that no two chemically coated faces touch.
Hard8Dynamic programmingCombinatoricsRecursionNo attempts yetTime limit2sMemory limit512 MBTadhg found a strip of tape in the school chemistry lab. The tape is divided into N segments of equal length. It bends at the boundary between two neighbouring segments, and only by exactly 180 degrees.
One face of the tape is completely covered with a highly volatile chemical. When that chemical touches itself, it reaches critical mass and explodes.
The other face is not covered everywhere yet. Only the first A segments and the last B segments carry the same chemical.
Bending the tape piles segments on top of each other in the same place. The tape cannot pass through itself, so the bent tape has to be a flat stack of segments. If two faces that touch inside that stack are both covered with the chemical, the tape explodes.
Write a program that counts the ways Tadhg can bend the tape without an explosion. He may bend it at several boundaries. Two ways are different when some boundary is bent in one way and is not bent in the other. The tape left unbent counts as one way.
The answer can be huge, so print it modulo 10301.

The picture above shows all 6 safe ways for N=4, A=1 and B=1. The tape is drawn bent by 90 degrees so that the layers stay visible, but Tadhg really bends it by 180 degrees.
The first and only line contains three natural numbers N, A and B: the total number of segments, the number of covered segments counted from the left, and the number of covered segments counted from the right. A>0, B>0, A+B≤N≤1000.
Print the number of ways to bend the tape without an explosion, modulo 10301.