Անհավասար զանգվածներ
Ինֆորմատիկայի և մաթեմատիկայի գիտակ Համլետը վերջերս հետաքրքրվում է անհավասար զանգվաներով։
n հատ ամբողջ թվերից կազմված զանգվածը անվանենք անհավասար, եթե այդ զանգվածի i-րդ պրեֆիքսային գումարը հավասար չէ i-րդ սուֆիքսային գումարին (չհաշված 0-րդը և n-րդը)։ Ֆորմալ n երկարության a զանգվածը կոչվում է անհավասար, եթե կամայական i թվի համար, որտեղ (1 ≤ i < n) տեղի ունի a1 + … + ai ≠ an-i+1 + … + an անհավասարությունը: Համլետին հետաքրքրում է n երկարության a զանգվածներեի քանակը, որոնք բավարարում են li ≤ ai ≤ ri անհավասարություններին, որտեղ (1 ≤ i ≤ n), իսկ l-ը և r-ը n երկարության տրված զանգվածներ են։ Համլետը շատ արագ կարողացավ հաշվել այդ քանակը, իսկ Դուք կարո՞ղ եք։ Քանի որ այդ քանակը կարող է շատ մեծ լինել, անհրաժեշտ է արտածել այդ թիվը 10^9+7-ի վրա բաժանելիս ստացված մնացորդը։Մուտքային տվյալներ
Առաջին տողում տրված է մեկ բնական թիվ
n (1 ≤ n ≤ 50)։ Հաջորդ n տողերից յուրաքանչուրում տրված են l և r զանգվածների հերթական տարրերը։Ելքային տվյալներ
Ելքում պետք է արտածել մեկ թիվ՝ տրված սահմանափակումներին բավարարող զանգվածների քանակը
10^9+7-ի բաժանելիս ստացված մնացորդը։Օրինակներ
Մուտք | Ելք |
5
1 2
1 1
1 2
1 2
1 2 | 6 |
Մուտք | Ելք |
7
1 3
2 3
1 2
1 3
2 3
1 3
1 3 | 288 |
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (6 միավոր)
n ≤ 20,ri≤ 2
- Ենթախնդիր 2 (23 միավոր)
ri≤ 3
- Ենթախնդիր 3 (15 միավոր)
ri≤ 15
- Ենթախնդիր 4 (20 միավոր)
ri≤ 50
- Ենթախնդիր 5 (36 միավոր) լրացուցիչ սահմանափակումներ չկան
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB