JADDOU3  Jaddouic Sequence
Jadou has created another boring sequence, he wrote the 1st 5 numbers on a stone, 300 years later Hasan Jadou Jr. found the stone and wanted to find the nth element of the sequence.
The numbers written on the stone were...
3, 10 , 36 , 136 ,528.
Jaddou junior descovered that the elements of the sequence are always even except the 1st one.
Help Jadou find the rest of the sequence.
print the nth element of the Jaddou sequence
mod 123456789
Input
One integer n.(0<n<10^18)
Output
The nth element of the Jaddou sequence mod 123456789.
Example
Input:
5
Output:
528
hide comments
Anubhav Balodhi :
20140213 14:02:14
Is the ans for 10^18 = 32810158 ?! Last edit: 20140213 14:24:28 

ROHIT RAWAT:
20131105 20:08:03
getting wa, although code is working for above cases. please tell me where it is going wrong


Pratyush Kumar:
20130810 18:59:19
Give more test cases.

Added by:  Aleksandar Abas 
Date:  20130327 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem 