cho.sh

And

K개의 음이 아닌 정수로 이루어진 수열의 합이 N이고 각 항이 다음 항과의 비트 AND와 같을 때, 그런 수열의 개수를 1e9+7로 나눈 나머지를 구한다.

어려움8동적 계획법비트 연산조합론수학아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

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хувааж үлдэгдлийг хэвлээрэй.