Помогите пожалуйста оптимизировать маленькую часть кода

[rekimchuk]

    
    m=7;
    for(int i=2; i<=n; i++)
    {
        m=(7*m) % 1000000000;
    }
    fout<<m;

мне нужны последние 9 цифр от возведение 7 в степень n. Но исп mod рядом с pow, с++ запрещает, по этому приходится такой код исп. слишком много времени тратится на эту задачу. Пробовал с шагом i+2 , и делать m*49 , но ответы уже не верны. пробовал и шаг i*i, и делать m*m всё равно ответ не верный.

[WorldMaster]

Что-то совсем не понятно как между собой вяжутся остаток от деления и последние цифры??

[rekimchuk]

Сообщение от WorldMaster

Что-то совсем не понятно как между собой вяжутся остаток от деления и последние цифры??

хм, чтоо? 25%10=5 ,25 поделить на 10 будет 2 и 5 остаток. у 25 , последняя цифра 5. именно с помощью mod или % находят последние цифры из больших чисел(ну или не больших)

[Black Fregat]

Быстрое возведение в степень по заданному модулю

unsigned long long powm(unsigned long long a, int n, unsigned long long m)
{
  unsigned long long res = 1;
  while (n > 0)
  {
    if (n & 1)
    {
      res = (res * a) % m;
    }
    a = (a * a) % m;
    n /= 2;
  }
  return res;
}

[rekimchuk]

Спасибо большое