Sofdor Ali and Radioactivity

Limits: 1.5s, 512 MB

Sofdor Ali is the craziest and clumsiest scientist in Bangladesh. He tries to maintain the safety measures perfectly. Yet due to his clumsiness, last month he blew his laboratory. Fortunately no one was injured or worse. Now after one month, he invented a new radioactive and explosive material. They are kept in a glass container. But there are some constraints. Blocks of container must be separated by lead separation. If more than M containers are placed side by side in a block, there cumulative radiation power will cause an explosion. Instead of keeping those materials in order, he thought of another problem, “How many ways can I do it?” Two arrangements are considered different if and only if they have different number of container blocks or they have same number of container blocks but there exists an index i for which size of i’th block differs in both arrangements. ( See the explanation of the third sample )

This is a companion discussion topic for the original entry at