Одним прекрасным утром n дураков выстроились в ряд. После этого они пронумеровали друг друга номерами от 1 до n включительно. Каждый дурак получил уникальный номер. Дураки решили не менять своих номеров до конца веселья.

У каждого дурака есть ровно k патронов и пистолет. Вероятность того, что дурак с номером i убьет дурака, в которого совершит выстрел, равна p_i процентов.

Дураки решили провести несколько раундов веселья. Каждый раунд веселья состоит в следующем: каждый еще живой дурак совершает выстрел в другого живого дурака с наименьшим номером (дураки не настолько глупы, чтобы стрелять в самих себя). Все выстрелы совершаются одновременно. Если остался ровно один живой дурак, то он не совершает выстрелов.

Назовем ситуацией множество номеров всех живых дураков на некоторый момент времени. Будем говорить, что ситуация возможна, если для некоторого целого числа j (0 ≤ j ≤ k) существует ненулевая вероятность, что через j раундов веселья будет иметь место именно такая ситуация.

Валера знает числа p₁, p₂, ..., p_n и k. Помогите Валере определить количество различных возможных ситуаций.