Problem Statement

Forbidden Arrangements Problem Description In the kingdom of Virelis, a coronation rite calls for N knights to be lined up in positions numbered 1 through N. Two old bans stand in the way of a straightforward lineup: Ban of Embers (A): a sequence A = [A 1 , A 2 , ..., A N ] stating that knight i may never occupy position A i . Ban of Frost (B): a second sequence B = [B 1 , B 2 , ..., B N ] stating that knight i may never occupy position B i . You must count how many ways the knights can be lined up while respecting both bans at once. In other words, count the valid lineups C = [C 1 , C 2 , ..., C N ] such that: No knight i occupies position A[i]. No knight i occupies position B[i]. Compute the total number of such valid lineups C. Because this count can grow very large, give the answer modulo 10 9 + 7. Input Format The first line contains an integer, N, denoting the number of elements in A. Each line i of the N subsequent lines (where 1 ≤ i ≤ N) contains an integer describing A[i