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 matter.
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
Sample Input
2
1
2
Sample Output
1
2
hide comments
include_sajal:
20170311 18:01:12
@Francky How did you to get to the editorial ?


Rishi Vikram:
20160130 14:02:47
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: 20160130 14:05:34 

Francky:
20150828 16:19:58
There are many such problems ; moved to tutorial. 
Added by:  likecs 
Date:  20150822 
Time limit:  0.300s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Own problem 