SPOJ OHANISER

Click here for Problem statement

Can this problem be solved without Modular exponentiation ?
I mean i have derived a formula for n if n is < even > !!
but not able to strike the formula for n < odd > . . if yes, can u please explain me how ?