Возникает переполнение при получении очередного числа последовательности

[FasterHarder]

Всем хай! Сразу к делу без всякой раскачки и не нужных прелюдий)

УСЛОВИЕ:
Некоторый ряд строится по правилу: A(i) = A(i - 2) + k * A(i - 1); A(1) = 0, A(2) = 1.
На вход подаются два числа: номер члена (от 1 до 40) и коэффициент к (от 1 до ляма). Нужно, используя рекурсию вывести последнюю цифру искомого члена.
Примеры ввода:
1 7, ответ 8
2 10, ответ 8
1000000 30, ответ 1
--------------------------------------
Код накропал и вроде все прекрасно, все тесты прошли КРОМЕ последнего, т к этот бешеный коэфф. явно приводит к переполнению. Пробовал поставить макс.мощный тип long double - не влезает вроде. В итоге вместо ответа = 1 выводит -1.

Вот сам код:

#include <iostream>
using namespace std;
 
long int F(const long long int pa, const long int pk)
{
    if(pa == 1)
        return 0;
    if(pa == 2)
        return 1;
    return (F(pa - 2, pk) + pk * F(pa - 1, pk));
}
void main(void)
{
    setlocale(LC_ALL, "");
    long long int k, m;
    cin >> k >> m;
    cout << F(m, k) % 10 << endl;
 
    cin.get();
    cin.get();
 
    return;
}

А может тут вовсе дело не в переполнении, хм...
Как побороть, чтобы проходил последний тест? Мемоизация или чего тут поможет

Добавлено 05.12.20, 10:07
форум вообще умер, да?) вижу на 1й странице аж сообщения за апрель)

[FasterHarder]

все, проблему решил, а форум скорее мертв, чем жыф)), но это и не важно...

[Qraizer]

Коли у тебя теперь C++, могу посоветовать boost::multiprecision. Это, что называется, в лоб. В целом же, конечно нет необходимости вычислять точный промежуточный результат рекуррентного алгоритма, тут возможно использовать арифметику остатков.

[FasterHarder]

Цитата Qraizer @ 05.12.20, 13:28

тут возможно использовать арифметику остатков.

ну, ты все правильно говоришь, как в общем-то и всегда)
здесь достаточно задействовать лишь младший разряд при сложении и умножении

я все это уже понял и сделал и все проходит на ура)

зы: Qraizer, на тебе держится форум еще из посл.сил))

[Black_Dragon]

Так надо просто посчитать или посчитать через рекурсию?