Zauważmy na początek, że istnieje dokładnie jedno ustawienie, które nie zawiera wież. Będziemy uznawali je za poprawne, a na końcu wynik zmniejszymy o 1. Możemy więc ustawić dowolną liczbę wież w dowolny sposób, byle się nie atakowały. Od tej pory problemy dla poszczególnych wierszy są niezależne. Łatwo zauważyć, że jeżeli wieże w jednym wierszu można ustawić na  sposobów, to ostatecznym wynikiem będzie reszta z dzielenia liczby przez  Do obliczenia tejże reszty wystarczy znać resztę z dzielenia liczby przez ; koszt czasowy końcowego potęgowania to 

Cały problem polega więc na wyznaczeniu wartości  Spróbujmy najpierw wyprowadzić wzór rekurencyjny na  Mamy następujące możliwości: albo pierwsze pole jest puste, a dalsza część planszy jest jakoś zapełniona wieżami, co daje  poprawnych ustawień, albo też na pierwszym polu stoi wieża, kolejne  pól jest pustych, a pozostałe są jakoś zapełnione, co daje dodatkowe  ustawień. Ostatecznie mamy, że Pozostaje zaznaczyć, iż dla przyjmujemy Daje to prosty algorytm obliczający  w czasie 

Inne rozwiązanie otrzymujemy, stosując standardową metodę obliczania wyrazów ciągu zadanego wzorem rekurencyjnym za pomocą szybkiego potęgowania macierzy, patrz artykuł Macierze oczami informatyka w  Delcie 7/2009. Przypomnijmy tylko, że w metodzie tej przedstawiamy taki oto wektor

jako iloczyn pewnej macierzy rozmiaru i analogicznego wektora zapisanego dla Wówczas zadanie sprowadza się do obliczenia macierzy  co możemy wykonać w czasie 

Spróbujmy teraz podejść do problemu od innej strony. Pokażemy, że sposobów ustawienia  wież w wierszu długości  jest tyle samo, co wyborów  elementów spośród elementów. Dla ustalenia uwagi przyjmijmy, że wieża zajmuje swoje pole oraz  pól na prawo od niego. W takim razie możemy skonstruować bijekcję między ustawieniami wież a wyborami elementów. Mając dane ustawienie wież, po prostu usuwamy  pól na prawo od każdej wieży poza ostatnią i otrzymujemy wybór  pól spośród pól. Odwrotnie, mając dany pewien wybór  elementów spośród elementów, ustawiamy wieże w polach odpowiadających tym elementom i po każdej (poza ostatnią) dokładamy dodatkowo  wolnych pól.

Żądanych ustawień wież jest zatem Oczywiście, musi być czyli

Aby obliczyć resztę z dzielenia przez wystarczy umieć szybko obliczać reszty z dzielenia symboli Newtona przez W tym celu korzystamy z twierdzenia Lucasa, które orzeka, że jeśli jest liczbą pierwszą i to daje taką samą resztę z dzielenia przez co Zauważmy teraz, że zarówno reszty z dzielenia liczb przez jak i ich odwrotności modulo możemy obliczyć w czasie  – te drugie według wzorów

Wówczas resztę z dzielenia przez  obliczamy w czasie stałym, natomiast ponownie zapisujemy w postaci i zaczynamy od początku. W ten sposób symbol Newtona obliczamy w czasie Możemy więc obliczyć  wykonując operacji. Można śmiało powiedzieć, że jest to  operacji, gdyż a zadanie jest interesujące tylko dla 

Żadne z powyższych rozwiązań nie jest jeszcze satysfakcjonujące. Aby uzyskać lepszy wynik, połączymy ostatnie dwa rozwiązania. Jeśli to uruchamiamy rozwiązanie z mnożeniem macierzy, a w przeciwnym przypadku rozwiązanie przez symbole Newtona. Ostatecznie, całe zadanie rozwiązujemy w czasie przy zużyciu pamięci rzędu