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.


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


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




Sample Input




Sample Output



hide comments
include_sajal: 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
Rishi Vikram: 2016-01-30 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: 2016-01-30 14:05:34
Francky: 2015-08-28 16:19:58

There are many such problems ; moved to tutorial.

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