Reducing the operation by using the modulo

Hi, I wonder that is there any way to disassemble this operation ((n+2^(n-2))^2 mod 1000000007) without counting 2^n-2. Please, help me.

 

"mod_pow" is a function (using fast modular exponentiation) which returns the result of exponentiation modulo 1000000007 - mod_pow (the first parameter, second parameter, modulo). The first parameter is the base, and the second parameter is the exponent.

For:
y <- n + mod_pow (2, n-2, 1000000007).
result <- mod_pow (y, 2, 1000000007).

I get an incorrect result, so I had misunderstood something. Very please to explain.

 

From the beginning I should explain what I want to achieve.

My work for the sequences of length 'n' is finding a number of variations elements of two-piece set, in this way that one of this two elements (doesn't matter which) will never occure next to another.
If set is composed just of '0' and '1' then possible combinations looks like this (I assume that element that will never appear next to another is ‘1’):
For n=2: 00 01 10 (result – 3)
For n=3: 000 001 010 100 101 (result - 5)
For n=4: 0000 0001 0010 0100 1000 1010 0101 1001 (result – 8)

I have to show result as: result^2 mod 1000000007. Maximum of 'n' is 2^31 -1 that is 2147483647. Maximum of calculating time is 1s.

One of my problems is to find a formula that gives me a number of combinations. I noticed some dependency between another results and I created a formula n+2^(n-2) for n>1, unfortunately I'm not 100% sure that this formula is correct ( I checked that for low 'n' this formula is correct).

My another problem is displaying a huge numbers. If n=2000000000 then calculating 2^(n-2) become impossible because of the size of result. However doing the calculations on string takes a lot of time.
Because of this it became obvious for me that I need to use fact that the final result have to be modulo 1000000007. At the beginning I turned in this forum with this problem.

On the web I found two implementations of modular exponentiation :

1: „unsigned long long int mod_pow(unsigned long long int num, unsigned long long int pow, unsigned mod)
{
　　unsigned long long int test,n=num;
　　for(test = 1; pow; pow >>= 1)
　　{
　　　　if (pow & 1)
　　　　　　test = ((test % mod) * (n % mod)) % mod;
　　　　n = ((n % mod) * (n % mod)) % mod;
　　}

　　return test;
}”

2: „unsigned long long int power_modulo_fast(unsigned long long int a, unsigned long long int b)
{
　　unsigned long long int x=a%1000000007,result=1,i;
　　for (i=1; i<=b; i<<=1)
　　{
　　　　x %= 1000000007;
　　　　if ((b&i) != 0)
　　　　　　{
　　　　　　　　result *= x;
　　　　　　　　result %= 1000000007;
　　　　　　}
　　　　x *= x;
　　}
　　return result;
}”


The final code is tested on the internet checker not on my computer, so parameters of my computer really doesn't matter.

I wrote a program for test which operating on strings so exponentiation 2^1000 isn't problem, but when I'm testing this program on my computer I get other result than those which I recived after using the above functions. Unfortunately I can't take this program as my official solution of this problem, because calculations takes a lot of time for higher data like n=1000000.

 

Here are the calculations that should be correct: http://img695.imageshack.us/img695/3950/calcw.png

My program returns the same result (the first based on a string and second without them). I also have exactly the same results as you. The problem is probably in the wrong set formula :/ I see no other option :/
Thank you very much for your help which was given to me here ;)

 

I send the source code for online judge, that evaluates the results, but the score for my program is "Wrong answer".

 

According to my formula for n=7, the number of combinations is 39, but I can’t find so many. If I don't find 39 combinations then the error is in formula.

Combinations which I could find (33):
0000000
0000001 0000010 0000100 0001000 0010000 0100000 1000000
1000001 1000010 1000100 1001000 1010000 0100010 0100001 0101000 0010010 0010100 0010001 0001001 0001010 0000101
1010001 1010010 1010100 0101010 0100101 0101001 1000101 1001010 1001001 0010101
1010101

 

Ok, I know. This is the Fibonacci series (2,3,5,8,13,21,34 ...).
How can I calculate: fib(n)^2 mod 1000000007, even for very large numbers?

Is it correct? https://ideone.com/cuGkK