Максим открыл свой собственный ресторан, в котором стоит огромный стол длины p метров.
Сегодня у Максима праздничный ужин, и к нему придет n гостей. Пронумеруем гостей ресторана Максима от 1 до n. Максим знает размеры всех гостей, которые к нему придут. Размер i-го гостя (ai) обозначает, сколько метров займет гость, если сядет за стол ресторана.
Задолго до ужина гости выстраиваются в очередь перед рестораном в некотором порядке. Затем Максим по очереди запускает гостей в свой ресторан. Максим перестает запускать гостей в ресторан в случае, если очередной гость не помещается за стол ресторана. Очередной гость не помещается за стол ресторана, если сумма размеров всех зашедших в ресторан гостей и размера очередного гостя больше p. В этом случае, чтобы не обидеть гостя, который не поместился за стол, Максим больше никого не пускает в ресторан, даже если один из следующих в очереди гостей помещается за стол ресторана.
Теперь Максиму интересно, чему равно среднее количество зашедших в ресторан гостей по всем n! возможным порядкам гостей в очереди. Помогите Максиму, посчитайте это число.
Примечание
В первом примере люди могут приходить в таких порядках:
- (1, 2, 3) — двое человек будет в ресторане;
- (1, 3, 2) — один человек будет в ресторане;
- (2, 1, 3) — двое человек будет в ресторане;
- (2, 3, 1) — один человек будет в ресторане;
- (3, 1, 2) — один человек будет в ресторане;
- (3, 2, 1) — один человек будет в ресторане.
В сумме получаем (2 + 1 + 2 + 1 + 1 + 1) / 6 = 8 / 6 = 1.(3).