Бобслей#736
Однією з найзахопливіших і найдраматичніших подій минулої Зимової Олімпіади у Ванкувері були змагання на бобслейній трасі. Організатори зробили трасу надзвичайно звивистою та швидкою. Подейкують, що для досягнення таких високих швидкостей спеціальний лід створювали з води, взятої з кількох канадських озер. Цю воду оцінювали за спеціальними характеристиками, а для визначення, яку воду використовувати на різних ділянках траси, застосовували секретну формулу.
За словами журналістів, кожну з ділянок траси наповнювали окремо. Для цього було надано всього зразків води. Кожен зразок оцінювався за придатністю для кожної ділянки, і ця придатність виражалась додатним цілим числом, що не перевищує 10^9. Тобто, кожен зразок мав оцінок придатності. Потім організатори обирали точно один зразок для кожної ділянки траси, і якщо сума цих характеристик дорівнювала , траса, заповнена такою комбінацією води, ставала максимально швидкою. Дозволяється використовувати один і той самий зразок води для різних ділянок, при цьому його характеристика для кожної ділянки може відрізнятися. Існує кілька способів вибору води, але досі ніхто не зміг визначити їх точну кількість.
У першому рядку задано через пробіл цілі числа , і (1 \leq N \leq 20000, 1 \leq S \leq 10^9, 2 \leq K \leq 3).
У наступних рядках міститься по цілих чисел, що розділені пробілами — спеціальні характеристики зразків води.
Виведіть єдине ціле число — кількість способів обрати по одному зразку для кожної ділянки траси.
Приклад 1