ให้ 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
โจทย์โดย: สุธี เรืองวิเศษ