Example from Wikipedia. Note thin line on a "waist" level - there parts separate.
We are indebted to Clive Fraser for creating this charming puzzle!
Traditional Russian Dolls, known as Matryoshka dolls, are actually a set of hollow wooden dolls of decreasing size, placed one inside another. Each of the component dolls is a wooden figure which separates at the middle, into an upper half (which we will call the Head) and a lower half (which we will call the Foot).
Vasily the doll maker has a large collection of Head and Foot sections of the component dolls. The component dolls are given a numeric size
from 1 to N. To make a component doll we need to combine a Head section with a Foot section of the same size. Since all of the pieces are
hand-made and hand painted, no two component dolls of the same size are the same. Just changing the Head or Foot section creates a different
doll. The complete Matryoshka doll consists of several component dolls, of decreasing size, with the smaller dolls inside the larger dolls.
For the purpose of this problem we will assume that Vasiliy has sufficient pieces to be able to make component dolls of all sizes from 1 to N.
We will also assume that the finished Matryoshka doll can consist of any number of component dolls from 2 to N. The sizes of the component
dolls used must all be different but there is no need for them to be consecutive.
Consider the following simple example. Vasily has Head sections in sizes 1, 2 and 3 and has one Head in each of these sizes. He also has
Foot sections in sizes 1, 2 and 3. He has one for each of sizes 1 and 3 but 2 Foot sections in size 2. This means that Vasily can
make 1 component doll in size 1 and 1 component doll in size 3. However, he has 2 possible ways of making the component doll in size 2
because of the two different Foot sections. If Vasily now makes one complete Matryoshka doll we want to know: How many different possible dolls
could he create?
If Vasily chooses to use all 3 sizes of component doll (1, 2 and 3) then there are 2 possible dolls that he could create, because of
the two alternatives for the component doll of size 2. If he makes a doll from sizes 1 and 2 only, there are again 2 possibilities
because of the 2 versions of component size 2. Similarly there are 2 ways of making a doll from sizes 2 and 3 only. Finally there is
just 1 way of making a doll from component sizes 1 and 3 only. In total, we have 2 + 2 + 2 + 1 = 7 different ways of making a complete
doll from the available pieces.
You will be given the numbers of Head and Foot pieces available in each of the sizes and are asked to calculate the number of different ways of
constructing a complete Matryoshka doll from the pieces available. The number of ways is likely to be very large, so you are asked to give the
answer modulo 1000000007 (10^9 +7). In order to generate the necessary data for the problem, we will use the
Linear Congruential Generator,
which has been used before in CodeAbbey problems. A random value X(n) is generated using the formula:
X(n) = (A * X(n-1) + C) % M
In this problem we will use the values A = 445, C = 700001 and M = 2097169. Note that % M means the remainder after dividing by the
modulus value of M. The value X(n-1) is the previous random value to be generated by this expression. In order to generate the first
random value X(1) we need to be given a value for X(0) which is called the seed for the generator. This value will be supplied as part of
the data for the problem. The formula above creates a reasonable sequence of roughly random values. However, these are much too large for this
problem. For each random value X(n) we will create the required number of pieces R(n), for a particular Head or Foot size, using the formula:
R(n) = 1 + X(n) %10
It should be obvious that the values of R(n) must be in the range 1 to 10 inclusive.
The example below is made deliberately small (N = 5) so that you can use it to test your ideas. It has only 5 sizes of doll (1 to 5).
The actual problem will be much larger. For the example, the random seed X(0) is taken to be 0 (it will not be 0 in the actual problem).
We need 5 numbers for the Head sizes and a further 5 numbers for the Foot sizes. The first 10 values generated for X(n) are
700001 1819434 840897 1603084 1034921 1959835 404272 244507 452828 880237
We need to apply the second formula to these in order to generate the values for R(n). These are
2 5 8 5 2 6 3 8 9 8
We will take the first 5 of these for the numbers of Head sections for sizes 1 to 5. The second 5 are then the numbers of Foot sections
for sizes 1 to 5. So, if we want to make a component doll of size 2, we have 5 Head sections and 3 Foot sections available; which
means that we can make 15 different versions of a component doll with this size.
Input/Output description: The first and only line of the input data will contain two space separated integers, the random seed X(0) and
the problem size N (which will be 3000 for the actual problem). You need to generate the numbers of each of the 6000 components using the
method outlined above. Your answer is the number of different ways of making a complete doll from the available pieces; give the answer modulo
1000000007.
Example:
input:
0 5
answer:
10572487