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.|
Problem hidden on 2020-10-30 17:45:28 by

ETDAQ004 - Nghịch bìa

Taekun có N miếng bìa và muốn viết lên mỗi miếng bìa một các số từ 1 đến 9 .Taekun băn khoăn không biết liệu có bao nhiêu cách viết số sao cho tổng các số trên tất cả N miếng bìa sẽ chia hết cho 9. Bạn tính giúp Taekun nhé.

Input

Dòng đầu tiên là số T <= 2000.

T dòng tiếp theo Có duy nhất một dòng chứa số nguyên dương N không quá 10^18

Output

Ghi ra số nguyên dương là số cách viết thỏa mãn (chia lấy dư cho 10^9 + 7).

Example

Input:
1
2

Output:
9

Được gửi lên bởi:ITPTIT Club
Ngày:2018-12-17
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:C C++ 4.3.2 CPP CPP14 JAVA PAS-FPC PYTHON3

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