Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P134SUMA - SUM4 A - Trò chơi với xúc sắc

Tí ở nhà phải trông em bé. Tí và nó cùng chơi cá ngựa. Nhưng thằng bé còn quá nhỏ nên nó không hiểu được trò chơi, nó cứ di chuyển tiến lùi con xúc sắc trên đường đi. Vì vậy, Tí lấy một dải ô vuông thẳng hàng có độ dài là n cho thằng bé thích nghịch thế nào thì tùy, không lại hỏng mất bàn cá ngựa của mình. Mỗi bước, thằng bé chỉ di chuyển con xúc sắc đi đúng một ô, và không đi ra ngoài giới hạn. Biết ban đầu Tí để con xúc sắc ở ô ngoài cùng bên trái, hỏi có bao nhiêu cách mà sau k bước, con xúc sắc sẽ ở vị trí ngoài cùng bên phải? 

Input

Dòng đầu tiên gồm 2 số n, m là độ dài của dải ô vuông và số trường hợp yêu cầu.

(2 <= n <= 10, m <= 50).

m dòng tiếp theo, mỗi dòng chứa một số nguyên k_i (k_i <= 10^9).

Output

Với mỗi trường hợp, hãy in ra số cách để sau k_i bước, con xúc sắc ở vị trí cuối cùng bên phải.
Vì đáp số có thể rất lớn nên lấy dư theo mod 1 000 000 007.

Example

Test 1:

Input:

4 4
3
4
5
15

Output:

1
0
3
377

 

Test 2:

Input:

2 4
1
2
3
4

Output:

1
0
1
0


Được gửi lên bởi:adm
Ngày:2013-07-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL6 PERL PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.