Cho hàm số \(f(n)\) được định nghĩa như sau:

Cho \(T\) bộ dữ liệu, mỗi bộ gồm các số \(n, a, b, c\). Hãy tính giá trị \(f(n)\) modulo \(10007\).

Input

• Dòng đầu tiên chứa số nguyên dương \(T\) là số lượng bộ dữ liệu.
• \(T\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(n, a, b, c\).

Output

• Với mỗi bộ dữ liệu, in ra một dòng theo định dạng Case X: Y, trong đó X là số thứ tự bộ dữ liệu (bắt đầu từ 1) và Y là giá trị \(f(n) \pmod{10007}\).

Constraints

• \(T \leq 10^2\)
• \(0 \leq n \leq 10^{18}\)
• \(1 \leq a, b, c \leq 10^4\)

Example

2
10 1 2 3
5 1 3 9

Case 1: 162
Case 2: 27