Шаблон блокування

Одним із способів блокування деяких телефонів є використання шаблону блокування. Щоб розблокувати телефон, потрібно намалювати секретний шаблон на сітці з певними точками, де шаблон складається з відрізків, що з'єднують ці точки.

Сітка шаблону вашого телефону складається з чотирьох рядків, у кожному з яких три точки. На наступному зображенні зліва показано представлення сітки, яке можна змоделювати як $2$D площину з координатами $X$ та $Y$ для кожної точки. Наприклад, верхня ліва точка має координати $(1,4)$, а нижня права — $(3,1)$. Зображення праворуч демонструє дійсний шаблон, який з'єднує точки в такому порядку: $(3,4)$ $(2,4)$ $(1,2)$ $(2,1)$ $(2,2)$ $(3,2)$ $(3,1)$ $(1,3)$.

Дійсний шаблон має такі властивості:

1. Шаблон може бути представлений послідовністю точок, яких він торкається вперше (у тому самому порядку, у якому малюється шаблон). Шаблон, що йде від $(1,1)$ до $(2,2)$, не є тим самим, що йде від $(2,2)$ до $(1,1)$.

2. Для кожної пари послідовних точок $A$ і $B$ у представленні шаблону, якщо відрізок, що з'єднує $A$ і $B$, проходить через інші точки, ці точки також повинні бути в послідовності і йти перед $A$ і $B$, інакше шаблон буде недійсним. Наприклад, представлення шаблону, яке починається з $(3,1)$, а потім $(1,3)$, є недійсним, оскільки відрізок проходить через $(2,2)$, яка не з'явилася в представленні шаблону перед $(3,1)$, і правильне представлення для цього шаблону — це $(3,1)$ $(2,2)$ $(1,3)$. Але шаблон $(2,2)$ $(3,2)$ $(3,1)$ $(1,3)$ є дійсним, оскільки $(2,2)$ з'явилася перед $(3,1)$.

3. У представленні шаблону ми не згадуємо ту саму точку більше одного разу, навіть якщо шаблон знову торкнеться цієї точки через інший дійсний відрізок, і кожен відрізок у шаблоні повинен йти від точки до іншої точки, якої шаблон ще не торкався, і він може проходити через деякі точки, які вже з'явилися в шаблоні.

4. Довжина шаблону — це сума манхеттенських відстаней між кожною парою послідовних точок у представленні шаблону. Манхеттенська відстань між двома точками (X_1, Y_1) і (X_2, Y_2) — це |X_1 - X_2| + |Y_1 - Y_2| (де $|X|$ означає абсолютне значення $X$). Довжина шаблону на зображенні вище: 1 + 3 + 2 + 1 + 1 + 1 + 4 = 13.

5. Шаблон повинен торкатися принаймні двох точок.

На жаль, ви забули шаблон вашого телефону, але пам'ятаєте довжину шаблону та набір точок $S$, яких точно не торкається шаблон (точки, які не входять до $S$, можуть торкатися або не торкатися шаблону), і ви вирішили спробувати всі дійсні шаблони, які відповідають тому, що ви пам'ятаєте. Перед тим, як це зробити, ви повинні написати програму, щоб підрахувати для вас кількість різних дійсних шаблонів.