Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P156SUMJ - ROUND 6J - Dãy số Fibonacci và phép toán UCLN

Tí được cô giáo ưu ái một bài tập đặc biệt về dãy Fibonacci như sau: Hãy tìm UCLN của 2 số A, B được xác định bởi công thức: A = a[0]F[n]+a[1]F[n+1]+a[2]F[n+2] và B = b[0]F[n]+b[1]F[n+1]+b[2]F[n+2].

Trong đó  là số Fibonacci thứ n. Dãy số Fibonacci được xác định bằng công thức truy hồi:

F[0] = 0, F[1] = 1; F[n] = F[n-1] + F[n-2].

Tí loay hoay một hồi chưa nghĩ ra cách giải quyết. Các bạn hãy giúp Tí nhé!

Input

Dòng đầu tiên là gồm số lượng bộ test T (T <= 100 000).

T dòng tiếp theo, mỗi dòng gồm 8 số nguyên n, a0, a1, a2, b0, b1, b2, M. Vì đáp số có thể rất lớn nên kết quả được lấy mod theo modulo M.

Giới hạn: n <= 10^15, 0 <= a[i], b[i] <= 1000, M <= 10^9.

Output

Với mỗi test, in ra số đáp án của bài toán.

Example

Input:

2

5 2 3 4 6 7 10 100

5 2 3 4 0 0 0 100

Output:

2

86

Giải thích test 1: Số fibo thứ 5, 6, 7 lần lượt là 5, 8, 13. Ta có A = 86, B = 216, ULCN(A, B) = 2.


Được gửi lên bởi:Admin
Ngày:2015-08-06
Thời gian chạy:2s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2016-06-13 14:41:55
MÌnh xin góp ý kiến:

- Mỗi bài post nên nói rõ đầu vào và đầu ra.(cái này quan trọng)
- Và mình không hiểu trình test online sẽ test = cách nào.

Mình chạy = code block thì ổn rồi, ra đúng kết quả. mà post nên thì báo làm sai.
2015-08-14 08:52:15 TICHPX
trong trường hợp a0=a1=a2=b0=b1=b2=0 thì out là gì nhỉ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.