Графические ключи на девяти точках

Экран блокировки телефона — сетка 3 × 3 из точек, пронумерованных так: 1 2 3 4 5 6 7 8 9 Графический ключ — это последовательность точек, которые палец соединяет по очереди прямыми отрезками. Ключ допустим, если: - все точки в нём разные; - отрезок между двумя соседними точками ключа не перепрыгивает через ещё не выбранную точку. Если отрезок проходит прямо через центр какой-то третьей точки, эта точка должна уже встретиться в ключе раньше. Например, переход 1 → 3 проходит через точку 2, поэтому он допустим только если 2 уже выбрана. А переход 2 → 9 ни через чей центр не проходит и разрешён всегда. Даны числа shortest и longest. Посчитайте, сколько существует допустимых ключей длиной от shortest до longest точек включительно. Ключи различаются набором точек или их порядком.

shortest=1, longest=1 → 9

shortest=2, longest=2 → 56

shortest=3, longest=2 → 0