#2341. CONSEQ

Trong cuộc thi tuyển sinh, có bạn tham gia. Ban tổ chức đã quyết định cho các bạn chơi một trò chơi như sau:

• bạn được sắp xếp thành một hàng dọc, đánh số theo thứ tự từ đến (người đầu hàng được đánh số là , người cuối hàng được đánh số là ).
• Mỗi bạn được Ban tổ chức phát cho một lá phiếu tương ứng với số hiệu của bạn đó, bạn đứng thứ trong hàng được ban tổ chức phát lá phiếu có số .
• Ban tổ chức chọn một bạn bất kỳ có để bắt đầu trò chơi, lần lượt các bạn đứng phía sau sẽ nói to số hiệu của mình. Ban tổ chức có thể kết thúc trò chơi bất kỳ lúc nào (kể cả khi bạn có vừa nói số hiệu của mình xong).
• Gọi là những người đã nói số hiệu của mình từ lúc bắt đầu cho đến khi kết thúc trò chơi. Dãy này cần thỏa mãn các điều kiện sau:
  • .
  • .
  • .
  • .

Để đánh giá mức độ đa dạng của trò chơi, Ban tổ chức cần phải biết có bao nhiêu dãy khác nhau thỏa mãn các điều kiện trên được tạo ra. Hai dãy và được gọi là khác nhau khi hoặc .

Yêu cầu: Bạn hãy giúp Ban tổ chức xác định xem có bao nhiêu dãy khác nhau thoả mãn các điều kiện nêu trên.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên dương ;
• Dòng thứ hai chứa số nguyên dương .

Dữ liệu ra:

• Gọi là số lượng dãy khác nhau thỏa mãn yêu cầu đề bài, cần in ra khi lấy phần dư với .

Ví dụ:

Dữ liệu vào:

3
1 2 3

Dữ liệu ra:

3

Dữ liệu vào:

6
1 2 3 1 2 3

Dữ liệu ra:

9

Dữ liệu vào:

5
2 3 4 5 6

Dữ liệu ra:

0

Giải thích:

• Trong ví dụ thứ nhất, các dãy thỏa mãn là: ;
• Trong ví dụ thứ hai, các dãy thỏa mãn là: ;
• Trong ví dụ thứ ba, không có dãy nào bắt đầu từ .

Giới hạn:

• .