Ռոբոտները շատ գործերում փոխարինում են մարդկանց։ Արտադրող ռոբոտները կոնվեյերի ժապավենի վրա դնում են երեք տեսակի դետալներ, նշանակենք դրանք {, ], 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 միավոր) Բոլոր [ սիմվոլները սկզբում են, բոլոր ] սիմվոլները վերջում են։