1134 : ลำดับ (sequence)
Problem type : Batch
Time limit : 0.3 second(s)
Memory limit : 32 megabyte(s)

ให้ A, B, C, D, E, F, G, H เป็นจำนวนเต็มใดๆ เราจะนิยามลำดับ a₁, a₂, a₃, … ดังนี้

a₁ = A, a₂ = B, a₃ = C, a₄ = D

และ a_k = Ea_k-1 + Fa_k-2 + Ga_k-3 + Ha_k-4 สำหรับทุกจำนวนเต็ม k ≥ 5

งานของคุณ
จงเขียนโปรแกรมเพื่อตอบคำถามทั้งหมด Q คำถามว่า สำหรับแต่ละค่า N เศษจากการหาร a_N ด้วย 2553 มีค่าเท่าไร

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม A, B, C, D, E, F, G และ H ซึ่งแต่ละจำนวนจะมีค่าอยู่ในช่วงตั้งแต่ 0 ถึง 1,000

บรรทัดที่ 2 ระบุจำนวนเต็ม Q (2 ≤ Q ≤ 200,000) แทนจำนวนคำถามทั้งหมด

อีก Q บรรทัดต่อมา ในบรรทัดที่ i+2 (1 ≤ i ≤ Q) จะระบุจำนวนเต็ม N (1 ≤ N ≤ 1,000,000,000,000,000,000) แสดงถึงคำถามที่ i

ข้อมูลส่งออก
มีทั้งหมด Q บรรทัด โดยในบรรทัดที่ i (1 ≤ i ≤ Q) แสดงคำตอบของคำถามที่ i

การให้คะแนน
20% ของข้อมูลทดสอบ จะมี N ≤ 1,000,000 ในทุกคำถาม
50% ของข้อมูลทดสอบ จะมี G = H = 0
60% ของข้อมูลทดสอบ จะมี Q ≤ 2,000

ที่มา
การแข่งขัน IOI Thailand League เดือนตุลาคม 2553
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
1 2 3 4 2 3 0 0 7 1 2 3 4 5 6 7	1 2 3 4 17 46 143
5 2 1 8 4 9 3 6 8 10 20 15 1 5 4 12 15	1127 2306 443 5 77 8 1598 443

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้