Bài tập

Số \(fib(n)\) với \(n \geq 0\) được tính theo công thức sau:

• \(fib(n) = n\) nếu \(n \leq 1\).
• \(fib(n) = fib(n - 1) + fib(n - 2)\) với \(n > 1\).

Yêu cầu: Cho ba số nguyên \(a, b, M\), gọi \(u\) là ước số chung lớn nhất của \(fib(a)\) và \(fib(b)\), hãy tính phần dư của phép chia \(u\) cho \(M\).

Input

Vào từ thiết bị vào chuẩn gồm ba số nguyên dương \(a, b, M\) \((a, b, M \leq 10^{12})\)

Output

Ghi ra thiết bị ra chuẩn một số là phần dư của phép chia \(u\) cho \(M\).

Example

6 9 10

2

Scoring

Subtask \(1\) với \(70\%\) số điểm : \(a, b, M \leq 50\).

Subtask \(2\) với \(20\%\) số điểm : \(a, b, M \leq 10^9\)

Subtask \(3\) với \(10\%\) số điểm : \(a, b, M \leq 10^{12}\)

Noel sắp tới, Ông Già Tuyết đã chuẩn bị \(2n\) món quà cho các bạn nhỏ. Các món quà có màu sắc đôi một khác nhau và có mã màu từ 1 đến \(2n\). Khi cho các món quà vào túi, Ông đã đưa ra các món quà vào theo một thứ tự mà nếu lấy ra, các món quà sẽ có mã màu lần lượt là \(c_1,c_2,…,c_{2n}\) (dãy \(c_1,c_2,…,c_{2n}\) là một hoán vị của \(1,2,…,2n\)).

Ông Già Tuyết dự định tặng quà cho \(m(m≤n)\) bạn nhỏ, mỗi bạn sẽ dược nhận hai món quà sau hai lượt tặng. Các bạn nhỏ đứng thành một hàng và Ông sẽ đi từ đầu hàng đến cuối hàng để lần lượt tặng quà cho từng bạn. Khi đứng trước một bạn nhỏ để tặng quà, Ông lần lượt lấy từng món quà ra cho tới khi lựa chọn được một món quà phù hợp và tặng bạn nhỏ, các món quà không được lựa chọn sẽ được cất đi và không được dùng để tặng quà. Khi bạn nhỏ thứ m ở cuối hàng đã được nhận quà, Ông sẽ di chuyển về đầu hàng để tặng quà lượt thứ hai tương tự như lượt thứ nhất.

Ông được biết, các bạn nhỏ luôn mong muốn nhận được hai món quà mà chênh lệch mã màu của hai món quà đó không vượt quá \(d\). Với mong muốn mang lại nhiều niềm vui cho các bạn nhỏ, Ông quyết định việc tặng quà sẽ phải đảm bảo tất cả các bạn nhỏ đều nhận được hai món quà mà chênh lệch mã màu không vượt quá \(d\).

Một cách hình thức, gọi \(m\) là số lượng bạn nhỏ được quà, Ông cần chọn ra dãy \(2m\) chỉ số \(1≤i_1<i_2<…<i_m<i_{m+1}<…i_{2m}≤2n\) sao cho \(|c_{i_k}−c_{i_{m+k}}|≤d\) với mọi \(1≤k≤m\).

Ông Già Tuyết biết rằng, có thể không tồn tại cách chọn được \(2m\) chỉ số thỏa mãn, điều đó cũng có nghĩa là không thể tặng quà như mong muốn cho cả \(m\) bạn nhỏ. Do đó, với một số nguyên dương \(d\) và thứ tự các món quà lấy ra có mã màu lần lượt là \(c_1,c_2,…,c_{2m}\), Ông muốn tính số lượng nhiều nhất các bạn nhỏ mà Ông có thể tặng quà.

Yêu cầu: Hãy giúp Ông Già Tuyết tính số lượng nhiều nhất các bạn nhỏ mà Ông có thể tặng quà đáp ứng điều kiện nêu trên.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(d(d \leq 5)\).

• Dòng thứ hai chứa \(2n\) số nguyên dương \(c_1,c_2,…,c_{2n}\) là mã màu của các món quà lần lượt được lấy ra.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số lượng nhiều nhất các bạn nhỏ mà Ông Già Tuyết có thể tặng quà.

Example

3 1
1 5 6 3 4 2

2

Scoring

• Có \(40\%\) số test tương ứng với \(40\%\) số điể của bài thỏa mãn \(n \leq 10\);

• \(40\%\) số test khác ứng với \(40\%\) số điểm của bài thỏa mãn \(n \leq 100\);

• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài thỏa mãn \(n \leq 1000\).

Có \(n\) thành phố và \(m\) chuyến bay kết nối giữa chúng. Bạn muốn đi từ Syrjälä đến Lehmälä để bạn đến thăm mỗi thành phố đúng một lần. Có bao nhiêu tuyến đường khả thi?

Input

• Dòng đầu tiên là hai số nguyên \(n\) và \(m\): số thành phố và chuyến bay. Các thành phố được đánh số \(1,2,\ldots, n\). Thành phố \(1\) là Syrjälä, và thành phố \(n\) là Lehmälä.

• Sau đó, có \(m\) dòng mô tả các chuyến bay. Mỗi dòng gồm hai số nguyên \(a\) và \(b\): có một chuyến bay từ thành phố \(a\) đến thành phố \(b\). Tất cả các chuyến bay đều là chuyến bay một chiều.

Output

• In ra một số nguyên: số tuyến đường theo modulo \(10^9 + 7\).

Example

4 6
1 2
1 3
2 3
3 2
2 4
3 4

2

Những người làm vườn có kinh nghiệm nhận thấy rằng nếu một quả cà chua chín đỏ (R) được đặt giữa những quả cà chua xanh (G) đã hái thì những quả cà chua xanh lân cận sẽ chín sau đúng một ngày.

Có \(n\) quả cà chua được xếp cạnh nhau thành một hàng, đánh số từ \(1\) đến \(n\).
Ba trong số những quả cà chua này đã chín, vị trí của chúng trong hàng là \(m_1, m_2, m_3\).

Yêu cầu: Hãy tìm số cà chua xanh còn lại sau \(d\) ngày.

Input

• Đọc từ tệp văn bản CAU1.INP gồm một dòng chứa năm số nguyên \(n, m_1, m_2, m_3, d\) \((4 \leq n \leq 10^{16}, 1 \leq m_i \leq n, i = 1,2,3, 1 \leq d \leq 10^{16})\).

• Các số cách nhau bởi dấu cách.

Output

• Ghi ra tệp văn bản CAU1.OUT gồm một dòng ghi một số là số cà chua xanh còn lại sau \(d\) ngày.

Example

19 2 13 15 2

8

50 1 50 25 7

19

Scoring

• \(50\%\) số điểm có \(n \leq 10^9\).

• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.