Masala #UGYSAG96BG

Xotira 5 MB Vaqt 600 ms Qiyinchiligi 50 %

Tanga tashlash 3

Bitboyda 1 tiyinlik tanga bor, uning bu tangasi ketma-ket tashlanganda hech qachon ketma-ket to'rt marotaba gerb tomoni bilan tushmaydi. Bitboy bu tangani ketma-ket N marotaba tashlaganda tanganing tushish ketma-ketligi variantlar sonini aniqlang.

Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, T(1 ≤ T ≤ 10⁵) testlar soni kiritiladi.

Har bir test uchun alohida satrda bitta butun son, N(1 ≤ N ≤ 10¹⁸) tanga tashlashlar soni kiritiladi.

Chiquvchi ma'lumotlar:

Chiqish faylida har bir test uchun alohida satrda so’ralgan javobni 10⁹+7 ga bo’lgandagi qoldiqni chop eting!

Misollar

#	input.txt	output.txt
1	4 1 2 3 4	2 4 8 15
2	1 1000	427794941

Izoh:

N=4 holatda bo'lishi mumkin bo'lgan kombinatsiyalar. (g=gerb ,s=so'm)

ssss, sssg, ssgs, sgss, gsss, ssgg, sgsg, sggs, gsgs, ggss, gssg, sggg, gsgg, gggs, ggsg. Jami 15ta holat

Telegram Facebook

Yechimini yuborish

Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin