In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
The ancient Babylonians decided to build a huge tower. The tower consists of
cubic building blocks that are stacked one onto another. The Babylonians gathered many building blocks of various sizes from all over the country. From
their last unsuccessful attempt they have learned that if they put a large block directly onto a much smaller block, the tower will fall.
Each two building blocks are different, even if they have the same size.
For each building block you are given its side length.
You are also given an integer with the following meaning: you
are not allowed to put block
directly onto block
if the side length of
is strictly larger than
plus the side length of
.
Compute the number of different ways in which it is possible to build the tower using all the building blocks.
Since this number can be very large, output the result modulo .
The first line of the input contains two positive integers and
:
the number of building blocks and the tolerance respectively.
The second line contains space-separated integers; each represents the size of one
building block.
All numbers in the input files are positive integers not exceeding .
is always at least 2.
In test cases worth 70 points will be at most 70.
Out of those, in test cases worth 45 points, will be at most 20.
Out of those, in test cases worth 10 points, will be at most 10.
For some of the test cases the total number of valid towers will not exceed . These test cases are worth 30 points in total.
For the last six test cases (worth 30 points) the value of is larger than 70. No upper bound on
is given for these test cases.
Output a single line containing a single integer: the number of towers that can be built, modulo .
For the input data:
4 1 1 2 3 100
the correct result is:
4
We can arrange the first three blocks in any order, except for or
. The last block has to be at the bottom.
For the input data:
6 9 10 20 20 10 10 20
the correct result is:
36
We are not allowed to put a cube of size 20 onto a cube of size 10. There are six ways to order the cubes of size 10, and six ways to order the cubes of size 20.
Task author: Michal Forisek.