eolymp
bolt
Try our new interface for solving problems
Məsələlər

A Huge Tower

A Huge Tower

The ancient Babylonians decided to build a huge tower. The tower consists of \textbf{N} 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 \textbf{D} with the following meaning: you are not allowed to put block \textbf{A} directly onto block \textbf{B} if the side length of \textbf{A} is strictly larger than \textbf{D} plus the side length of \textbf{B}. 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 \textbf{10^9+9}. \InputFile The first line of the input contains two positive integers \textbf{N} and \textbf{D}: the number of building blocks and the tolerance respectively. The second line contains \textbf{N} space-separated integers; each represents the size of one building block. \textbf{Constraints} All numbers in the input files are positive integers not exceeding \textbf{10^9}. \textbf{N} is always at least \textbf{2}. In test cases worth \textbf{70} points \textbf{N} will be at most \textbf{70}. Out of those, in test cases worth \textbf{45} points, \textbf{N} will be at most \textbf{20}. Out of those, in test cases worth \textbf{10} points, \textbf{N} will be at most \textbf{10}. For some of the test cases the total number of valid towers will not exceed \textbf{1000000}. These test cases are worth \textbf{30 }points in total. For the last six test cases (worth \textbf{30} points) the value of \textbf{N} is larger than \textbf{70}. No upper bound on \textbf{N} is given for these test cases. \OutputFile Output a single line containing a single integer: the number of towers that can be built, modulo \textbf{1000000009}.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
4 1
1 2 3 100
Çıxış verilənləri #1
4
Müəllif Michal Forišek