20250509

#include <stdio.h>

int memo[100000]={0};

int cha(int n)

{

if(n==0)

{

return 0;

}

if(memo[n]!=0)

{

return memo[n];

}

n=n*2+1;

return memo[n]=cha(n)+n%100007;

}

int main()

{

int n;

scanf("%d",&n);

int k=cha(n);

k=k%100007;

printf("%d",k);

return 0;

}