他们的额头正中探出一只长角，也只有这只长角全部呈柔和的白色。角非常之细，纤纤欲折。较之
角，倒更令人想起由于某种偶然的机会陡然刺破皮肤支出体外而后就势固定下来的一条细骨。除去角的
白色和眼睛的蓝色，兽的其他部位统统一色金黄。它们试穿新衣似的上下抖动几下脖子，朝着寥廓的秋
空高扬起角尖，继而把脚浸进日益发凉的河流。伸长脖子吞食树上红色的果实。
……
当号角声弥漫小镇的时候，兽们便朝太古的记忆扬起脖颈——超过一千头之多的兽们以一模一样的
姿势一齐朝号角声传来的方向昂首挺颈。勉为其难地咀嚼金雀草的停止咀嚼，蹲在卵石路面用蹄甲囊囊
叩击地面的停止叩击，仍在最后一袭夕照中午睡未醒的睁眼醒来，分别朝空中伸长脖颈。
……
但这仅仅是暮色中的幻想，一睁眼水泡即杳然逝去。有的只是兽的蹄音，小镇仍一如往常。兽们的
队列如河水流过弯弯曲曲的卵石路面，没有哪个带头，也没有哪个领队。兽们低眉垂首，瑟瑟抖动肩头，
默默向前涌动。但看上去每一头之间仍被无可消除的亲密记忆的纽带紧紧相连，尽管并不显而易见。
它们由北向下走过旧桥，同从东边沿河流南岸走来的同伴汇合后，顺着运河穿过工厂区，向西走过
铸铁工厂的槽廊，翻过西面的山麓，在西山坡等待队列临近的是无法离门太远的老兽和幼兽。它们在那
里向北通过西桥，抵达门口。
走在前头的兽们刚到门前，看门人便把门打开。门是用纵横交错的厚铁板加固过的，一看就知其又
重又结实。门高4 米至5 米，上面针山一般密密麻麻排列着尖钉，以防有人越门而过。看门人十分轻快
地将这沉重的门扇朝前拉开，把云集而来的兽们放出门外。门是对开的，但看门人总是只开一扇，左边
那扇始终岿然不动。兽们一头不剩地过完之后，看门人又把门关严，上好锁。
……
据我所知，西门是这座小镇的惟一出入口。镇的四周围着高达七八米的长墙，惟独飞鸟可过。
清晨来临，看门人再次开门，吹响号角将兽们放入门内。待兽们全部进来后，仍如上次那样关门上
锁。
……
“为什么傍晚把兽们集中起来赶去门外，而早上又叫到里边来呢？”我见看门人的意识已恢复如初，
便试着询问。
看门人以不含有任何感情的神色定定看了我一会。
“这样规定的嘛。”他说，“这样规定了就得这样做，和太阳东出西落是一个道理。”
……
小镇的一天便这样落下了帷幕。
村上春树《世界尽头与冷酷仙境》
Chapter 2 世界尽头——金毛兽
小M 的男朋友一年前读了村上春树的《世界尽头与冷酷仙境》，冥冥之中他想到——
小镇上一共有n 只独角兽，它们的能力值分别为1 ∼ n
每天清晨，独角兽们会排成一列进入城门。当一只能力值为x 的独角兽进入城门后，看门人便会获
得x 个水晶。当看门人手中的水晶数大于0 且是3 的倍数的时候，或者当所有独角兽都进入了城门，看
门人便会关闭城门。
为了让所有独角兽都顺利进入小镇，有多少种独角兽可能的排列顺序？
有多少种n 的全排列A，满足以下条件：
Bi =
Σi
j=1 Aj ; ∀i ∈ [1; n − 1]; 3 ̸ | Bi
请给出答案%10000000000037 的结果。
Input
第一行一个整数T，表示数据组数。
对于每组数据，一行一个整数n 表示独角兽个数。
Output
一行一个整数表示答案。
Examples
unicorn.in
1
4
unicorn.out
6
unicorn.in
2
461350
946122
unicorn.in
unicorn.out
8077061242588
9686440545236
Notes
对于所有数据，满足0 ≤ T ≤ 3; 3 ≤ n ≤ 3 × 109。
Subtask1[3pts]
T = 0
Subtask2[26pts]
n ≤ 8
Subtask3[24pts]
n ≤ 103
Subtask4[10pts]
n ≤ 3 × 106
Subtask5[14pts]
n ≤ 3 × 107
Subtask6[11pts]
n ≤ 3 × 108
Subtask7[12pts]