Πούλι στην σκακιέρα

Σε μια σκακιέρα, ένα πούλι μπορεί να ακολουθήσει πολλά μονοπάτια για να φτάσει στην απέναντι πλευρά.

Ακολουθεί ένα παράδειγμα για το πώς ένα πούλι σε μια σκακιέρα $4⇥4$ μπορεί να φτάσει στην απέναντι πλευρά μέσω 5 διαδρομών. Οι αριθμοί στα τετράγωνα αντιπροσωπεύουν τα διαφορετικά μονοπάτια που μπορείτε να ακολουθήσετε για να φτάσετε σε κάθε τετράγωνο:

Στην παρακάτω εικόνα έχουμε μια σκακιέρα $8⇥8$, όπου το πούλι μπορεί να κινηθεί μόνο διαγώνια προς τα κάτω για να παραμείνει στο δικό του χρώμα και δεν μπορεί να περάσει μέσα από ένα τετράγωνο με ένα ${\rm X}$.

Ο στόχος είναι να προσδιορίσετε πόσες διαδρομές μπορεί να ακολουθήσει το πούλι για να φτάσει στο απέναντι πλευρά του ταμπλό.