# Sequence Creation ARCRT SOLUTION Code Chef

Page Contents

## Sequence Creation ARCRT SOLUTION Code Chef

Chef has two sequences of integers (A1,A2,…,AN)(A1,A2,…,AN) and (B1,B2,…,BN)(B1,B2,…,BN).

A sequence of integers is beautiful if it contains only distinct integers. For each valid ii:

• Chef wants to create a beautiful sequence SiSi. Let’s denote the length of this sequence by LiLi and the sequence by Si,1,Si,2,…,Si,LiSi,1,Si,2,…,Si,Li.
• The sequence SiSi is good if for each valid jj, Si,jSi,j is either equal to Ai+j−1Ai+j−1 or Bi+j−1Bi+j−1. Note that this means LiLi must be at most N−i+1N−i+1.
• Let’s denote the maximum possible value of LiLi (the maximum value such that some good sequence SiSi with this length exists) by MiMi.
• Help Chef find the number of good sequences SiSi that have the maximum possible length MiMi. Since this number may be enormous, compute it modulo 109+7109+7.

### Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains a single integer NN.
• The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
• The third line contains NN space-separated integers B1,B2,…,BNB1,B2,…,BN.

### Output

For each test case, print a single line containing NN space-separated integers. For each valid ii, the ii-th of these integers should be the number of possible sequences SiSi modulo 109+7109+7.

### Constraints

• 1≤T≤1,0001≤T≤1,000
• 1≤N≤1051≤N≤105
• |Ai|,|Bi|≤109|Ai|,|Bi|≤109 for each valid ii
• the sum of NN over all test cases does not exceed 5⋅1055⋅105

• N≤1,000N≤1,000
• the sum of NN over all test cases does not exceed 5⋅1035⋅103

Subtask #2 (80 points): original constraints

```2
4
2 2 3 2
2 3 4 4
5
1 2 2 3 3
2 1 2 3 1
```

### Example Output

```1 2 3 2
2 1 1 1 2
```

### Explanation

Example case 1:

• S1S1 can only be (2,3,4)(2,3,4).
• S2S2 can be (2,3,4)(2,3,4) or (3,4,2)(3,4,2).
• S3S3 can be (3,2)(3,2), (3,4)(3,4) or (4,2)(4,2).
• S4S4 can be (2)(2) or (4)(4).

Example case 2:

• S1S1 can be (1,2)(1,2) or (2,1)(2,1).
• S2S2 can only be (1,2,3)(1,2,3).
• S3S3 can only be (2,3,1)(2,3,1).
• S4S4 can only be (3,1)(3,1).
• S5S5 can be (3)(3) or (1)(1).