{"code":"2024febplatinum1","name":"USACO 2024 February Contest, Platinum, Lazy Cow","description":"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$.\r\n\r\nNô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})$.\r\n\r\nGọ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$.\r\n\r\n#### Input\r\n\r\nDò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.\r\n\r\n#### Output\r\n\r\nIn ra $D$ dòng, dòng thứ $i$ chứa $e_i$  $mod$  $10^9+7$\r\n\r\n#### Scoring\r\n- Subtask $1$: $D\\le100$  và $m_i \\le 100$\r\n- Subtask $2$: $D\\le3000$ \r\n- Subtask $3$: Không có điều kiện gì thêm\r\n\r\n#### Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```\r\n        4 \r\n        5 11 \r\n        6 10 \r\n        10 15 \r\n        10 30 \r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        21 \r\n        21 \r\n        25 \r\n        90 \r\n        ```\r\n    ??? warning \"Note\"\r\n    \r\n        Với test mẫu thứ nhất.\r\n        \r\n        - $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$\r\n        - $i=2$: Bessie có thể làm giống ngày $1$.\r\n        - $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.\r\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.\r\n        \r\n        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.\r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```\r\n        2 \r\n        100 5 \r\n        100 1000000000000 \r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        5 \r\n        627323485 \r\n        ```\r\n!!! question \"Test 3\"\r\n    ???+ \"Input\"\r\n        ```\r\n        20\r\n        303590 482848034083\r\n        180190 112716918480\r\n        312298 258438719980\r\n        671877 605558355401\r\n        662137 440411075067\r\n        257593 261569032231\r\n        766172 268433874550\r\n        8114 905639446594\r\n        209577 11155741818\r\n        227183 874665904430\r\n        896141 55422874585\r\n        728247 456681845046\r\n        193800 632739601224\r\n        443005 623200306681\r\n        330325 955479269245\r\n        377303 177279745225\r\n        880246 22559233849\r\n        58084 155169139314\r\n        813702 758370488574\r\n        929760 785245728062\r\n        ```\r\n    ???+ \"Output\"\r\n        ```\r\n        108753959\r\n        108753959\r\n        108753959\r\n        148189797\r\n        148189797\r\n        148189797\r\n        148189797\r\n        32884410\r\n        32884410\r\n        32884410\r\n        32884410\r\n        32884410\r\n        32884410\r\n        32884410\r\n        3883759\r\n        3883759\r\n        3883759\r\n        3883759\r\n        3883759\r\n        3883759\r\n        ```","points":1000.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}