NEWCURR - New Currency Shopping

Imagine that you have only one rupee and two rupee coin with you. Given a sum “n” to pay to the shopkeeper using only these 2 coins, in how many ways can it be done? Since the answer can be pretty large, print the answer modulo “12345678901”. Also, the order in which the coins were given matters.

Input

The first line contains the number of test cases ‘t’. Then t lines follow, each having a number ‘n’.

Output

For each number ‘n’ output the corresponding answer, after modulo operation.

Constraints

T <= 10^4

1 <= N <= 10^18

Example

Sample Input
2
1
2

Sample Output
1
2

Added by:likecs
Date:2015-08-22
Time limit:0.300s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem

hide comments
2017-03-11 18:01:12
@Francky How did you to get to the editorial ?

=(Francky)=> Ancient EB( zukow, alias :D ) propose to admins to set me EB. Some times after that, I proposed Mitch as EB, and some times after Min_25 to join us. There are some other EBs, some active, more or less. I hope I answered your question.

Last edit: 2017-03-11 19:22:09
2016-01-30 14:02:47 Rishi Vikram
Taking modulo after every operation, still the answer overflows. Do we have to multiply using arrays? MODULO is very large, MOD*MOD overflows

Last edit: 2016-01-30 14:05:34
2015-08-28 16:19:58 Francky
There are many such problems ; moved to tutorial.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.