Đế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 ≤ n ≤ 10^{18}; 1 ≤ k ≤ 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

Nguồn: 2021 Thi thử