Find all combinations of a number sequence which is first increasing then decreasing
Bug

Input : 500000003
Output: 18446744073709551615


The problem is that the result of your power() call could be 0 or 1.  Then when you subtract 2, you get a negative number.  Given the input constaint of \$n ≤ 10^9\$, 500000003 is the only bad input, but in general this happens when n is any multiple of 500000003.  To correct this, you could change this:


temp--;
temp--;



to:

temp = (temp + m - 2) % m;


This ensures that temp will remain positive.  Time complexity wise, your program is great at \$O(\log n)\$.