Đếm số cách chia các số nguyên dương từ ~1~ đến ~n~ vào hai nhóm sao cho mọi cặp hai số khác nhau thuộc cùng một nhóm có tổng không thuộc tập ~k~ số cho trước. ~k~ số này là luỹ thừa của ~2~.

Input

Gồm không quá ~10000~ test. Mỗi test bắt đầu bằng một dòng chứa ~2~ số nguyên ~n~ và ~k~ ~(1 \leq n \leq 10^{18}~; ~1 \leq k \leq 61)~. Dòng thứ hai chứa ~k~ số nguyên dương là luỹ thừa của ~2~ và không vượt quá ~2n~.

Dữ liệu kết thúc bằng một dòng chứa hai số ~0~.

Output

Với mỗi test, ghi ra số cách phân nhóm theo modulo ~1000000007~.

Sample Input

5 1
1
4 2
4 2
0 0

Sample Output

32
8