USACO 2024 February Contest, Platinum, Lazy Cow

Tác giả:

Dạng bài

Điểm: 1000 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Bessie đang chuẩn bị bài tập cho cuộc thi USA Cowmputing Olympiad vào tháng \(2\). Mỗi phút, cô ấy có thể chọn không chuẩn bị bài tập nào và không tốn sức lực; hoặc dùng \(3^{a-1}\) năng lượng để chuẩn bị \(a\) bài, \(a > 0\).

Nông dân John có \(D (1\le D \le 2*10^5)\) yêu cầu. Với yêu cầu thứ \(i\), Bessie cần phải chuẩn bị ít nhất \(b_i\) bài trong \(m_i\) phút. \((1 \le m_i \le 10^6, 1 \le b_i \le 10^{12})\).

Gọi \(e_i\) là lượng năng lượng tiêu thụ ít nhất Bessie cần để hoàn thành yêu cầu thứ \(i\). In ra \(e_1,…,e_D\) \(mod\) \(10^9+7\).

Input

Dòng đầu chứa số tự nhiên \(D\). Dòng thứ \(i\) trong \(d\) dòng tiếp theo chứa 2 số nguyên \(m_i\) và \(b_i\) cách nhau bởi dấu cách.

Output

In ra \(D\) dòng, dòng thứ \(i\) chứa \(e_i\) \(mod\) \(10^9+7\)

Scoring

Subtask \(1\): \(D\le100\) và \(m_i \le 100\)
Subtask \(2\): \(D\le3000\)
Subtask \(3\): Không có điều kiện gì thêm

Example

Test 1

Input

Output

Note

Với test mẫu thứ nhất.

\(i=1\): Nếu Bessie tạo ra \([2,3,2,2,2]\) bài tập vào \(5\) ngày đầu, mỗi ngày cô ấy sẽ tốn \(3^1+3^2+3^1+3^1+3^1=21\) đơn vị năng lượng để tạo ra 11 bài vào cuối ngày thứ \(5\)
\(i=2\): Bessie có thể làm giống ngày \(1\).
\(i=3\): Nếu Bessie tạo \([2,3,2,2,2,0,1,1,1,1]\) trong \(10\) ngày đầu, cô ấy sẽ tiêu tốn \(25\) đơn vị năng lượng và hoàn thành yêu cầu. Có thể thấy không có chiến thuật nào tốt hơn.
\(i=4\): Nếu 10 ngày đầu, mỗi ngày Bessie tạo 3 bài thì cô ấy sẽ tiêu tốn \(3^2*10=90\) đơn vị năng lương và hoàn thành yêu cầu.

Với mỗi \(i\), Bessie sẽ không thể thỏa mãn yêu cầu nếu dùng ít năng lượng hơn.

Test 2

Input

2 
100 5 
100 1000000000000

Output

5 
627323485

Test 3

Input

20
303590 482848034083
180190 112716918480
312298 258438719980
671877 605558355401
662137 440411075067
257593 261569032231
766172 268433874550
8114 905639446594
209577 11155741818
227183 874665904430
896141 55422874585
728247 456681845046
193800 632739601224
443005 623200306681
330325 955479269245
377303 177279745225
880246 22559233849
58084 155169139314
813702 758370488574
929760 785245728062

Output

Bình luận

Không có bình luận nào.