Ռոբոտներ
Ռոբոտները շատ գործերում փոխարինում են մարդկանց։ Արտադրող ռոբոտները կոնվեյերի ժապավենի վրա դնում են երեք տեսակի դետալներ, նշանակենք դրանք {, ], I սիմվոլներով։ Հավաքող ռոբոտը պետք է սկզբում վեցնի մի հատ [ տեսակի դետալ, ապա նրա վրա դնի առնվազն մեկ I տեսակի դետալ, և վերջում մեկ հատ ] տեսակի դետալ։ Հարկավոր է հաշվել տարբեր հավաքածուների քանակը, որ հավաքող ռոբոտը կարող է կազմել։
Ավելի ֆորմալ, տրված է n երկարության [, I, ] սիմվոլների հաջորդականություն։ Հարկավոր է հաշվել այդ հաջորդականությանը պատկանող այն ենթահաջորդականությունների քանակը, որոնց առաջին սիմվոլը [ է, վերջին սիմվլոը ] է, իսկ մնացած սիմվոլները I են, ընդ որում I սիմվոլների քանակը պետք է զրոյից մեծ լինի։
Մուտքային տվյալներ
Առաջին տողում տրված է հաջորդականության
n (1 ≤ n ≤ 10^) երկարությունը։ Երկրորդ տողում տրված է հաջորդականությունը։ Երկրորդ տողում բացատանիշեր չկան։Ելքային տվյալներ
Պետք է արտածել մեկ թիվ՝ խնդրի պայմաններին բավարարող ենթահաջորդականությունների քանակը։ Քանի որ պատասխանը կարող է շատ մեծ թիվ լինել, հարկավոր է արտածել այն
10^9+7-ի բաժանելուց մնացորդը։Օրինակ
Մուտք | Ելք |
6
[[I]I] | 8 |
Օրինակի բացատրություն
Ենթահաջորդականությունները ներկայացնենք իրենց տարրերի ինդեքսների միջոցով, համարակալումը սկսած զրոյից․
0 2 3
0 2 5
0 2 4 5
0 4 5
1 2 3
1 2 5
1 2 4 5
1 4 5
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակները
- Ենթախնդիր 1 (12 միավոր)
1 ≤ n ≤ 20
- Ենթախնդիր 2 (15 միավոր)
1 ≤ n ≤ 1000
- Ենթախնդիր 3 (18 միավոր) Բոլոր [ սիմվոլները սկզբում են, բոլոր ] սիմվոլները վերջում են։
- Ենթախնդիր 4 (55 միավոր) Լրացուցիչ սահմանափակումներ չկան։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB