Устройство с тачскрином может быть разблокировано с помощью "пароля", состоящего из последовательности из двух или больше различных точек, которые пользователь выбирает на прямоугольной решетке точек на экране. Пользователь вводит пароль путем касания первой точки, затем проведения отрезка до следующей точки, и так далее до конца последовательности. Палец пользователя при этом не отрывается от экрана и может двигаться по прямым отрезкам от точки к точке.

Если палец прочерчивает линию, проходящую через промежуточную точку, то это считается как два последовательных отрезка и промежуточная точка включается в последовательность пароля. Например, на решетке $3\times 3$, пронумерованной цифрами от $1$ до $9$ (см. ниже), проведение пальцем от $1$ до $9$ будет воспринято как последовательность $1-5-9$.

После того, как точка была выбрана, она пропадает с экрана. С этого момента эта точка больше не может быть использована как конечная точка последующих отрезков и она игнорируется в случае, если последующие отрезки будут проходить через нее. Например, проведение пальцем по $1-9-3-7$ (при это точка $5$ пересекается дважды) даст пароль $1-5-9-6-3-7$.

Существует $389488$ различных паролей, которые можно образовать на сетке $3 \times 3$.

Найдите количество различных паролей, которые можно образовать на сетке $4 \times 4$.