Bobsleigh#736
One of the most thrilling and dramatic events at the last Winter Olympics in Vancouver was the bobsled track competition. The organizers designed the track to be extremely winding and fast. It is rumored that to achieve such high speeds, special water from several Canadian lakes was used to create the ice. This water was assessed based on special characteristics, and a secret formula was used to determine which water to use for different sections of the track.
According to journalists, each of the sections of the track was filled separately. A total of water samples were provided for this purpose. Each sample was rated for its suitability for use in each section, with the suitability expressed as a positive integer not exceeding 10^9. Thus, each sample had suitability ratings. Then, the organizers selected exactly one sample for each section of the track, and if the sum of these characteristics equaled , the track filled with this combination of water became maximally fast. It is allowed to use the same water sample for different sections, but its characteristic may differ for each section. There are several ways to select the water, but no one has been able to determine the exact count so far.
The first line contains integers , , and separated by spaces (1 \leq N \leq 20000, 1 \leq S \leq 10^9, 2 \leq K \leq 3).
The next lines each contain integers separated by spaces—the special characteristics of the water samples.
Output a single integer—the number of ways to select one sample for each section of the track.
Example 1