16080번 - And 다국어

문제

N ба K бүхэл хоёр тоо өгөгдөнө. Таны даалгавар бол K гишүүнтэй дарааллын тоог олох юм. Дараалал нь дараах нөхцөлийг хангах ёстой.

• A₁ + A₂ + A₃ + ... + A_k = N
• A_i+1 = A_i & A_i+1, (хоёртын үржих буюу ба үйлдэл) i = 0,1,2,...,K-1;

입력

Эхний мөрөнд тестийн тоо болох T-г илэрхийлэх эерэг бүхэл ганц тоо өгөгдөнө. (0 ≤ T ≤ 10)

Дараагийн Т-ширхэг мөрөнд хоёр эерэг бүхэл тоо болох K (0 ≤ K ≤ 10⁵) ба N (0 ≤ N ≤ 10⁴) тоо өгөгдөнө.

출력

Тест бүрийн хариуг ганц мөрөнд хэвлэнэ. Бодлогын хариу том тоо байж болох тул 10⁹+7хувааж үлдэгдлийг хэвлээрэй.

제한

힌트