electicode
HomeCoursesResourcesProblemsNational OlympiadContestsLeaderboard
...

Aquilla

Time Limit: 2000msMemory Limit: 512MB
View Submissions

Problem Description

You are given a sequence of NNN pairs of natural numbers (di,vi)(d_i, v_i)(di​,vi​), for iii from 111 to NNN.

A subsequence of indices 1≤i1<i2<⋯<ik≤N1 \leq i_1 < i_2 < \cdots < i_k \leq N1≤i1​<i2​<⋯<ik is called if for every two consecutive indices and , where , the difference is divisible by

Your task is to determine the sum of the products vi1×vi2×…×vikv_{i_1} \times v_{i_2} \times \ldots \times v_{i_k}vi1​​×vi2​​ over all non-empty clever subsequences, modulo .

Input Format

The input file contains the natural number NNN (1≤N≤2⋅1051 \leq N \leq 2 \cdot 10^51≤N≤2⋅105) on the first line.

The second line contains NNN natural numbers d1,d2,…,dNd_1, d_2, \ldots, d_Nd1​,d2​,…,dN​ (), separated by spaces.

The third line contains NNN natural numbers v1,v2,…,vNv_1, v_2, \ldots, v_Nv1​,v2​,…,vN​ (), separated by spaces.

Output Format

The output must contain a single natural number, representing the sum of the products of all non-empty clever subsequences, modulo 109+710^9 + 7109+7.

Scoring

SubtaskPointsConstraints
111666N≤20N \leq 20N≤20
2221313

Examples

Example 1
Input
3
2 3 2
1 10 100
Output
211
Explanation

We have N=3N = 3N=3 pairs: (2,1)(2, 1)(2,1), (3,10)(3, 10)(3,10) and (2,100)(2, 100).

© 2026 Electicode. All rights reserved.

​
≤
N
clever
ipi_pip​
ip+1i_{p+1}ip+1​
1≤p<k1 \leq p < k1≤p<k
ip+1−ipi_{p+1} - i_pip+1​−ip​
min⁡(dip,dip+1).\min(d_{i_p}, d_{i_{p+1}}).min(dip​​,dip+1​​).
×
…×
vik​​
109+710^9 + 7109+7
1≤di≤1091 \leq d_i \leq 10^9
1≤di​≤109
1≤vi≤1091 \leq v_i \leq 10^9
1≤vi​≤109
13
N≤2⋅103N \leq 2 \cdot 10^3N≤2⋅103
333777N≤2⋅105N \leq 2 \cdot 10^5N≤2⋅105 and di=1d_i = 1di​=1 for every 1≤i≤N1 \leq i \leq N1≤i≤N
444777N≤2⋅105N \leq 2 \cdot 10^5N≤2⋅105 and 1≤di≤21 \leq d_i \leq 21≤di​≤2 for every 1≤i≤N1 \leq i \leq N1≤i≤N
555141414N≤2⋅105N \leq 2 \cdot 10^5N≤2⋅105 and 1≤di≤2001 \leq d_i \leq 2001≤di​≤200 for every 1≤i≤N1 \leq i \leq N1≤i≤N
666121212N≤105N \leq 10^5N≤105 and the sequence ddd is increasing
777222222N≤105N \leq 10^5N≤105
888191919No additional constraints
(2,100)

Let us analyze all possible non-empty subsequences of indices:

  • (1)(1)(1): valid by definition, because it contains only one element. The product is v1=1v_1 = 1v1​=1.
  • (2)(2)(2): valid. The product is v2=10v_2 = 10v2​=10.
  • (3)(3)(3): valid. The product is v3=100v_3 = 100v3​=100.
  • (1,2)(1, 2)(1,2): the difference of indices is 2−1=12 - 1 = 12−1=1. Also, min⁡(d1,d2)=min⁡(2,3)=2. \min(d_1, d_2) = \min(2, 3) = 2. min(d1​, Since is not divisible by , this subsequence is not clever.
  • (2,3)(2, 3)(2,3): the difference of indices is 3−2=13 - 2 = 13−2=1. Also, min⁡(d2,d3)=min⁡(3,2)=2. \min(d_2, d_3) = \min(3, 2) = 2. min(d2​, Since is not divisible by , this subsequence is not clever.
  • (1,3)(1, 3)(1,3): the difference of indices is 3−1=23 - 1 = 23−1=2. Also, min⁡(d1,d3)=min⁡(2,2)=2. \min(d_1, d_3) = \min(2, 2) = 2. min(d1​, Since is divisible by , this subsequence is clever. The product is
  • (1,2,3)(1, 2, 3)(1,2,3): since the adjacent pairs (1,2)(1, 2)(1,2) and (2,3)(2, 3)(2,3) do not satisfy the condition, this subsequence is not clever.

Therefore, the sum of the products of all clever subsequences is 1+10+100+100=211.1 + 10 + 100 + 100 = 211.1+10+100+100=211. Thus, the answer is 211 mod (109+7)=211211 \bmod (10^9 + 7) = 211211mod(109+7)=211.

d
2​
)
=
min(2,3)=
2.
111
222
d
3​
)
=
min(3,2)=
2.
111
222
d
3​
)
=
min(2,2)=
2.
222
222
v1⋅v3=1⋅100=100. v_1 \cdot v_3 = 1 \cdot 100 = 100. v1​⋅v3​=1⋅100=100.