Пусть a_n - последовательность, заданная в рекурсивном виде: .

Первые 10 элементов a_n таковы: 1,1,0,3,0,3,5,4,1,9.

Обозначим через f(N,M) число пар (p,q), удовлетворяющих требованиям:

Нетрудно убедиться, что f(10,10)=4, и эти пары - (3,3), (5,5), (7,9) и (9,10).

Помимо этого, известно, что f(10⁴,10³)=97158.

Найдите f(10¹²,10⁶).