В компании из \(n\) человек организуется поход в кинотеатр. Каждый человек может либо пойти, либо нет. Это зависит от того, сколько ещё народу пойдёт. А именно, каждый человек \(i\) сказал: «Я хочу пойти в кинотеатр тогда и только тогда, когда пойдут хотя бы ещё \(a_i\) других человек, не считая меня». Это значит, что \(i\)-й человек расстроится в двух случаях:
- если он пойдёт в кинотеатр, а кроме него пойдут строго менее \(a_i\) других человек; или
- если он не пойдёт в кинотеатр, но при этом пойдут хотя бы \(a_i\) других человек.
Сколько есть способов выбрать множество людей, идущих в кинотеатр, чтобы никто не расстроился?
Выходные данные
Для каждого набора входных данных выведите одно целое число — число различных способов выбрать множество людей, идущих в кинотеатр, чтобы никто не расстроился.
Примечание
В первом наборе входных данных оба человека хотят пойти тогда и только тогда, когда другой человек пойдёт. Есть два подходящих варианта: либо оба пойдут, либо оба не пойдут. Если же пойдёт лишь один из двоих, то оба окажутся расстроены.
Во втором наборе входных данных в кинотеатр должны пойти все. В любом другом варианте обязательно кто-нибудь расстроится.
В третьем наборе входных данных есть три допустимых варианта: либо идёт человек с номером \(2\); либо идут люди с номерами \(2, 3, 4, 7\); либо идут все восемь человек.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3
|
2
1
3
2
|