Permütasiya

Besi'nin 2D şəbəkəsində, heç bir üçü kollinear olmayan n sevimli nöqtəsi var. Hər bir i üçün (1 ≤ i ≤ n), i-ci nöqtə iki tam koordinatla x[i] və y[i] (0 ≤ x[i], y[i] ≤ 10^4) ilə verilir.

Besi nöqtələr arasında bəzi seqmentləri aşağıdakı qaydada çəkir:

• O, n nöqtədən bir sıra p[1], p[2], .., p[n] seçir;

• O, p[1] və p[2], p[2] və p[3], p[3] və p[1] arasında seqmentlər çəkir;

• Sonra hər bir tam i üçün 4-dən n-ə qədər ardıcıl olaraq, p[i]-dən p[j]-ə qədər seqmentlər çəkir, burada j < i və bu seqment əvvəllər çəkilmiş heç bir seqmenti kəsmir (son nöqtələrdən kənarda).

Besi fərq etdi ki, hər bir i üçün o, dəqiq üç yeni seqment çəkdi. 1-ci addımda Besi'nin seçə biləcəyi və bu xüsusiyyəti təmin edən permutasiyaların sayını 10^9 + 7 modulunda hesablayın.

Giriş Məlumatları

Birinci sətir n (3 ≤ n ≤ 40) ehtiva edir.

Sonrakı n sətirin hər biri iki tam ədəd x[i] və y[i] ehtiva edir.

Çıxış Məlumatları

10^9 + 7 modulunda permutasiyaların sayı.

Nümunə 1

Heç bir permutasiya işləməyəcək.

Nümunə 2

Bütün permutasiyalar işləyir.

Nümunə 3

Xüsusiyyəti təmin edən permutasiyalardan biri - (0, 0), (0, 4), (4, 0), (1, 2), (1, 1). Bu permutasiya üçün:

Əvvəlcə o, hər bir cüt arasında (0, 0), (0, 4) və (4, 0) seqmentlərini çəkir.

Sonra o, (0, 0), (0, 4) və (4, 0) nöqtələrindən (1, 2)-yə seqmentlər çəkir.

Nəhayət, o, (1, 2), (4, 0) və (0, 0) nöqtələrindən (1, 1)-ə seqmentlər çəkir.

Permutasiya xüsusiyyəti təmin etmir, əgər onun ilk dörd nöqtəsi (0, 0), (1, 1), (1, 2) və (0, 4) müəyyən bir qaydada olarsa.