ФИФА је увела неочекивано правило пред финале светског првенства у фудбалу. Уместо \(11\) играча на терену, сада сваки тим има \(N\) играча и играчи су нумерисани бројевима од \(1\) до \(N\) (бројеви им се, наравно, налазе на дресу).

Финале је у току и Меси има озбиљну шансу за гол. Уколико терен посматрамо као координатни систем, Месијева тренутна координата је \((0, 0)\), а координата француског фудбалера са дресом број \(k\) је \((x_k, y_k)\) (за свако \(1 \leq k \leq N)\).

Меси је веома интелигентан играч и мало је познато да је заправо и сјајан такмичарски програмер. Зато, узео је да посматра своје противнике како би нашао слабост.

Он посматра свих \(2^N - 1\) непразних подскупова француских играча. Да би одредио квалитет своје шансе, потребно му је да сазна колико подскупова постоји, таквих да конвексни омотач тачака фудбалера тог подскупа - садржи тачку \((0,0)\). Пошто овај број може бити веома велик, потребно је исписати његов остатак при дељењу бројем \(10^9+7\).

Ово му не би правило проблем да је код куће за рачунаром и ради српске квалификације за окружно такмичење, али пошто је у финалу Светског првенства, потребна му је ваша помоћ.

Напомена: Конвексни омотач скупа тачака \(S\) дефинишемо на следећи начин:

• уколико се у \(S\) налази само једна тачка, конвексни омотач је само та тачка;
• уколико се у \(S\) налази скуп колинеарних тачака (све тачке на истој правој), конвексни омотач је најкраћа дуж која садржи све тачке;
• у супротном, конвексни омотач је конвексни многоугао најмање површине који садржи све тачке скупа \(S\).

Рачунамо да конвексни омотач садржи тачку и у случају да се тачка налази на некој од ивица конвексног омотача.

Опис улаза

Прва линија стандардног улаза садржи један цео број \(N\) - број играча у тиму по новим правилима. У \(k\)-тој од наредних \(N\) линија налази се по два цела броја \(x_k\), \(y_k\) - координате противничког играча са бројем дреса \(k\).

Опис излаза

У јединој линији стандардног излаза, исписати остатак броја непразних подскупова француских играча у чијем конвексном омотачу се налази Меси, након што га поделимо бројем \(10^9+7\).

Пример 1

Улаз

5
3 -1
8 -1
-9 1
7 -1
-4 1

Излаз

9

Објашњење

Одговарајући непразни подскупови играча су:

• \(\{1, 2, 3, 4, 5\}\)
• \(\{1, 2, 3, 5\}\)
• \(\{1, 2, 4, 5\}\)
• \(\{1, 2, 5\}\)
• \(\{1, 3, 4, 5\}\)
• \(\{1, 4, 5\}\)
• \(\{2, 3, 4, 5\}\)
• \(\{2, 3, 5\}\)
• \(\{3, 4, 5\}\)

Пример 2

Улаз

18
25 32
36 40
-13 7
-26 -49
3 27
-33 -39
-19 -9
36 6
-16 -31
-17 -48
-29 34
-49 36
-28 -25
7 37
2 45
-18 15
-23 -26
41 42

Излаз

239247

Ограничења

• \(1 \leq N \leq 10^5\).
• \(-10^9 \leq x_k, y_k \leq 10^9\), за \(1 \leq k \leq N\).
• \((x_k, y_k) \neq (x_j, y_j)\), за \(1 \leq k < j \leq N\).
• \((x_k, y_k) \neq (0, 0)\), за \(1 \leq k \leq N\).

Тест примери су подељени у 5 дисјунктних група:

• У тестовима вредним 10 поена: \(N = 3\).
• У тестовима вредним 10 поена: \(y_1 = 1\) и \(y_k = -1\), за \(1 < k \leq N\).
• У тестовима вредним 25 поена: \(y_k \in \{-1, 1\}\), за \(1 \leq k \leq N\).
• У тестовима вредним 15 поена: \(N \leq 18\).
• У тестовима вредним 40 поена: Без додатних ограничења.