Masala #IJESLNO11U

Vali sizni yaqin do'sti deb biladi, Vali hozir IELTS imtixoniga tayyorlanayotgani uchun bu masalani yechishni sizga ishonib topshirdi:

Tasavvur qiling sizda \(A\) massiv bor, boshlanishiga bu massiv 1 dan \(N\)gacha bo'lgan sonlardan tashkil topgan. \(N-1\) marta shu massiv ustida quyidagi amallarni bajarishingiz kerak.

• Massivdan istalgan 2 ta \(X\) va \(Y\) sonlarni tanlang.
• Tanlangan elementlarni massivdan o'chirib tashlang.
• Massivga \(X+Y+X*Y\) sonini qoshing.

Natijada massivda 1 ta elemnt qoladi. Shu sonning maksimal qiymatini toping?

Birinchi qatorda \(T(1\leq T\leq10^5)\) testlar soni

Kegingi \(T\) ta qatorda \(N(1\leq N\leq10^6)\) soni

Har bir test uchun massivni o'zgartirishdan hosil bo'lishi mumkin bo'lgan maximum sonni \(10^9+7\) ga bo'lgandagi qoldigini chop eting.