I think, it's a simple recursion.
If N is even, then
f(N)=f(N-1)+f(N/2)
else if N is odd, then
f(N)=f(N-1)
Am I right?

mod P also important espacially if P==1

I count it at the end before the output.
There is my code:
#include <iostream>
using namespace std;

__int64 FindAnswer(const __int64 &num);

int main(void)
{
   // Input data
   __int64 K, P;
   cin >> K >> P;
   // Outputs the result
   cout << (FindAnswer(K)%P) << endl;
   return 0;
}
// Function finds the answer
__int64 FindAnswer(const __int64 &num)
{
   if(num==2)
      return 1;
   if(num<2)
      return 0;
   if(num%2)
      return num/2;
   return FindAnswer(num-1) + FindAnswer(num/2);
}

It should to combine recursion and Dynamic prog.
At the beggining build array F1[10000000] using formula and
from K>10000000 go by recursion not to 1 as you
but only to first value in [1..10000000]
But %P we must make in FindAnswer befor return
or we will have overflow and i don't understand
conditiom if (num%2)
must be if (num%2==0)

To Duzhy Igor
Your solution has non polynomial complexity

Why you are using this way
Just fill array[2..10000000] from 2 to k using your formula
at the end out (mas[k]%p)

Edited by author 05.03.2007 17:00

Thank you very much, I have solved it. Good luck!!!