陈犇的数学题
题号：NC15767
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 64 M，其他语言128 M
64bit IO Format: %lld

题目描述

陈犇说: 校赛得有一道数学题, 于是有了这样一道题
已知一个关于n的函数:
                                       
陈犇有q次询问, 每次他会告诉你一个正整数m, 你需要回答陈犇: f(m)对1000003取模(余)之后的结果

输入描述:

第一行包含一个正整数q, 代表陈犇的询问次数
接下来q行中, 第i行包含一个正整数mi, 代表陈犇所询问的数字

输出描述:

输出包含q行, 第i行包含一个非负整数, 代表回答陈犇: f(mi)%1000003的值
示例1

输入

复制 
1
1

输出

复制 
1

说明

陈犇有1个询问: 这个询问是m=1, 此时:

备注:

1≤q≤105且为整数
1≤mi≤109且为整数

其中的定义为: 不超过x的最大整数
例如: