Trò Chơi Hoán Vị Vòng
Points
60
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Đề bài
Cho một hoán vị $P$ của $N$ phần tử (từ 1 đến $N$). Bạn được phép thực hiện thao tác "next permutation" nhiều lần. Bạn cần tìm số bước ít nhất để biến $P$ thành hoán vị $Q$ cho trước. Nếu $Q$ đứng trước $P$ theo thứ tự từ điển, thì bạn cần đi qua hoán vị cuối ($N, N-1, \ldots, 1$) rồi quay lại hoán vị đầu ($1, 2, \ldots, N$) và tiếp tục.
Vì kết quả có thể rất lớn, in ra số bước modulo $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$.
- Dòng thứ hai chứa hoán vị $P$.
- Dòng thứ ba chứa hoán vị $Q$.
Dữ liệu ra
- In ra số bước modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 3 1 2 3 2 1 3 |
2 |
| 3 2 1 3 1 3 2 |
5 |
Giới hạn
- $1 \le N \le 12$
Community Discussion