시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB37201450.000%

문제

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

  • A1 + A2 + A3 + ... + Ak = N
  • Ai+1 = Ai & Ai+1, (хоёртын үржих буюу ба үйлдэл) i = 0,1,2,...,K-1;

입력

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

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

출력

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

예제 입력 1

2
2 3
2 5

예제 출력 1

1
2