, чтобы сохранить свой прогресс
Задача 408: Допустимые пути через сетку
Назовем точку решетки (x, y) недопустимой, если x, y и x + y - все положительные совершенные квадраты. Например, (9, 16) недопустимо, а (0, 4), (3, 1) и (9, 4) - нет.
Рассмотрим путь от точки (x1, y1) до точки (x2, y2), используя только единичные шаги на север или восток. Назовем такой путь допустимым, если ни одна из его промежуточных точек недопустима.
Пусть P (n) - число допустимых путей от (0, 0) до (n, n). Можно проверить, что P (5) = 252, P (16) = 596994440 и P (1000) mod 1 000 000 007 = 341920854.
Найти P (10 000 000) mod 1 000 000 007.
/**
* Your test output will go here.
*/