eolymp
bolt
Try our new interface for solving problems
Problems

Подарки

Подарки

Time limit 1 second
Memory limit 64 MiB

Дед Мороз хочет подарить всем уникальные подарочные наборы ровно из M предметов. Для этого у него есть неограниченное количество предметов, относящимся к N классам (фрукты, игрушки, косметика и т.д.). В каждом классе можно выделить также несколько категорий предметов, например, в класс фрукты попадают яблоки, апельсины, груши и т.д. Все предметы, относящиеся к одной категории, являются одинаковыми. Дед Мороз не хочет, чтобы в одном наборе оказалось несколько предметов, относящихся к одному классу, например, яблоко и апельсин или два яблока.

Напишите программу, которая по числу классов и числу категорий в каждом классе определит количество различных подарочных наборов из M предметов, которые сможет сформировать Дед Мороз. Подарочные наборы являются различными, если они отличаются хотя бы одной категорией входящих в них предметов.

Input data

Во входном файле в первой строке содержатся два целых числа N и M (0  < M  ≤ N  ≤  10), разделенных пробелом – количество классов и количество предметов в наборе. Во второй строке содержится N целых чисел от 1 до 10, разделенных пробелами – количество категорий в каждом классе.

Output data

В выходной файл вывести одно число – количество различных подарочных наборов из M предметов.

Examples

Input example #1
3 2
2 3 4
Output example #1
26