Классическая задача о восьми ферзях - хорошо известная головоломка о расположении восьми шахматных ферзей на шахматной доске 8×8 так, чтобы никакие два ферзя не угрожали друг другу. Если считать повороты и отражения одного и того же расположения фигур различными расположениями, можно найти всего 92 возможных различных расположения для восьми ферзей. В общем случае стоит вопрос о количестве возможных различных расположений n ферзей на доске n×n. Например, существует 2 различных расположения для n=4.

Определим слабого ферзя на доске n×n как фигуру, которая может двигаться на любое количество клеток по горизонтали, но максимум - на n−1−w клеток по верикали или диагонали, где 0≤w<n - "фактор слабости". Например, слабый ферзь на доске n×n с фактором слабости w=1, расположенный в нижнем ряду, не сможет угрожать ни одной клетке верхнего ряда, так как слабому ферзю понадобилось бы переместиться на n−1 клеток по вертикали или диагонали, чтобы туда добраться, но он может двигаться только на n−2 клеток в этих направлениях. В то же время, слабый ферзь не ограничен в движении по горизонтали, и, таким образом, угрожает каждой клетке своего ряда, независимо от его положения в этом ряду.

Пусть Q(n,w) будет количеством способов расположения n слабых ферзей с фактором слабости w на доске n×n так, чтобы никакие два ферзя не угрожали друг другу. Можно показать, например, что Q(4,0)=2, Q(4,2)=16 и Q(4,3)=256.

Пусть $S(n)=\displaystyle\sum_{w=0}^{n-1} Q(n,w)$.

Известно, что S(4)=276 и S(5)=3347.

Найдите S(14).