Trong một thời xa xưa, nơi rừng sâu và núi cao gặp nhau, có một ngôi làng độc đáo. Không ai biết tên của ngôi làng này, nhưng mọi người gọi nó là Ngôi làng của các Số Đẹp. Ở đây, số không chỉ là con số. Nó là một phần của cuộc sống hàng ngày, là nguồn cảm hứng và niềm tự hào. Mọi người trong làng đều yêu thích số, và họ không ngừng khám phá những tính chất kỳ diệu của chúng. Trong vai khách du lịch ở làng, bạn được phép tham gia vào trò chơi của người dân ở đây.

Bạn được cho một số nguyên dương ~n~, hãy tìm số cách khác nhau để biểu diễn ~n~ dưới dạng tổng của các số nguyên dương đối xứng. Biết rằng số nguyên dương đối xứng khi nó vẫn giữ nguyên sau khi đảo ngược thứ tự các chữ số của nó. Ngoài ra, hai cách được coi là khác nhau nếu tần suất xuất hiện của ít nhất một số nguyên đối xứng khác nhau trong chúng khác nhau. Ví dụ, ~5=1+1+1+1+1~ và ~5=1+2+2~ được coi là hai cách khác nhau, nhưng ~5=1+2+2~ và ~5=2+1+2~ được coi là như nhau. Nói cách khác, bạn cần tìm tập hợp các số nguyên dương đối xứng có tổng bằng ~n~.

Vì số cách có thể rất lớn nên bạn cần phải in ra kết quả khi lấy dư với ~10^9+7~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~t~, số câu hỏi mà bạn nhận được.
• ~t~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~n~.

Dữ liệu ra

Gồm ~t~ dòng, mỗi dòng in ra số cách tương ứng khi lấy dư với ~10^9+7~.

Giới hạn

• Subtask ~1(20\%)~: ~t \le 10~ và ~n \le 10~.
• Subtask ~2(80\%)~: ~t \le 10^4~ và ~n \le 4\times 10^4~.

Ví dụ

Dữ liệu vào

3
1
4
12

Dữ liệu ra

1
5
74

Giải thích

• Với ~n=1~, ta có ~1=1~ là một cách duy nhất.
• Với ~n=4~, ta có ~4~ cách:
  • ~4=1+1+1+1~
  • ~4=1+1+2~
  • ~4=1+3~
  • ~4=2+2~
  • ~4=4~
• Với ~n=12~, ta có ~74~ cách.