Số BEAUTIQ

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một số \(X\). Ta gọi \(BQ(X)\) là số BeautiQ thứ \(X\).

Số BeautiQ được xác định qua công thức như sau:

  • \(BQ(0)=A,BQ(1)=B\), với \(A,B\) cho trước.
  • \(BQ(X)=BQ(X−1)+BQ(X−2)+BQ(X−1) \times BQ(X−2). \ (X \geq 2)\)

Cho \(Q\) truy vấn, truy vấn thứ \(i\) gồm 3 số nguyên dương \(N_i,A_i,B_i\). Với truy vấn thứ \(i\), tính \(BQ(N_i)\) \(mod\) \((10^9+7)\) với \(BQ(0)=A_i,BQ(1)=B_i\).

Input

  • Dòng đầu tiên chứa số nguyên dương \(Q\) là số truy vấn.
  • \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa 3 số nguyên dương \(N_i,A_i,B_i\) thể hiện cho truy vấn thứ \(i\).

Output

  • Ghi ra \(Q\) dòng, dòng thứ \(i\) là kết quả cho truy vấn thứ \(i\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(Q \leq 10^2;N_i,A_i,B_i \leq 5 \times 10^5\).
  • Subtask \(2\) (\(70\%\) số điểm): \(Q \leq 10^4;N_i \leq 10^{18};A_i,B_i \leq 10^{12}\)

Example

Test 1

Input 
2
5 1 1
4 2 5
Output 
255
1943

Bình luận