“千年等一回 等一回啊“
“千年等一回 我无悔啊”
“是谁在耳边 说 爱我永不变”
“只为这一句 啊哈断肠也无怨”
白蛇传是中国古代民间爱情传说故事之一。发生在宋朝时的杭州、苏州及镇江等地。白素贞是千年修炼的蛇妖，为了报答书生许仙前世的救命之恩，化为人形欲报恩，后遇到青蛇精小青，两人结伴。白素贞施展法力，巧施妙计与许仙相识，并嫁与他。婚后金山寺和尚法海对许仙讲白素贞乃蛇妖，许仙将信将疑。后来许仙按法海的办法在端午节让白素贞喝下带有雄黄的酒，白素贞不得不显出原形，却将许仙吓死。白素贞上天庭盗取仙草将许仙救活。
白娘子盗仙草的时候，被看守仙草的童子发现了，童子正在想一道数学题，想不出来，抓到了白娘子，所以嘿嘿一笑，要白娘子来想这道题，否则就要把白娘子盗仙草的事情禀报给天庭。
这道题是这样的，告诉你一个$n$，$m=1^{10000}+2^{10000}+……n^{10000}$,问m除以3的余数是多少？
白娘子法力无边，所以召唤了一个锦囊。
锦囊里写着：
设$p$除以$c$的余数是$a$，$q$除以$c$的余数是$b$。
若$m=(p+q)$
则$m\%c = (a+b)\%c$;
若$m=p\cdot q$
则$m\% c=(a\cdot b)\% c$
$(p\cdot p\cdot p)\% c = (p\%c)\cdot (p\%c)\cdot (p\%c)$
为了救活许仙，请你帮白娘子做一下这道题。
对于每组输入，输出一行，即算式的余数。
锦囊里的知识或许可以帮你解决这道题