기dp{l,r}dpl,r는 l,rl,r 이 단수가 형성할 수 있는 답안의 총계를 나타낸다.
매거진 마지막 동작 kk, 곱셈이면 답은 dp{l,k}*dp_{k+1,r}dpl,k∗dpk+1,r 분배율 때문에 곱할 수 있습니다.덧셈이라면 dp{l,r}*(r-k-1)!+dp_{k+1,r}*(k-l)!dp​l,r​​∗(r−k−1)!+dp​k+1,r​​∗(k−l)!,즉, 오른쪽 k+1, rk+1, r 이 수를 곱해서 모든 실행 가능한 방안수를 감법은 같은 이치이다.마지막으로 {r-l-2\choose k-l}(k-3 l r-3 l-3)을 곱하면 양쪽 조작을 합친 방안수이다.
정답은 dp{1,n}dp​1,n​​.

Expression

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 447    Accepted Submission(s): 260
Problem Description
Teacher Mai has 
n  numbers 
a1,a2,⋯,an and 
n−1  operators("+", "-"or "*")
op1,op2,⋯,opn−1 , which are arranged in the form 
a1 op1 a2 op2 a3 ⋯ an .
He wants to erase numbers one by one. In 
i -th round, there are 
n+1−i  numbers remained. He can erase two adjacent numbers and the operator between them, and then put a new number (derived from this one operation) in this position. After 
n−1  rounds, there is the only one number remained. The result of this sequence of operations is the last number remained.
He wants to know the sum of results of all different sequences of operations. Two sequences of operations are considered different if and only if in one round he chooses different numbers.
For example, a possible sequence of operations for "
1+4∗6−8∗3 "is 
1+4∗6−8∗3→1+4∗(−2)∗3→1+(−8)∗3→(−7)∗3→−21 .
 
Input
There are multiple test cases.
For each test case, the first line contains one number 
n(2≤n≤100) .
The second line contains 
n  integers 
a1,a2,⋯,an(0≤ai≤109) .
The third line contains a string with length 
n−1  consisting "+","-"and "*", which represents the operator sequence.
 
Output
For each test case print the answer modulo 
109+7 .
 
Sample Input

   
   
   
   

    
    
    
    3
3 2 1
-+
5
1 4 6 8 3
+*-*
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
999999689

    
    
    
    
 
     
 
      Hint 
     
 Two numbers are considered different when they are in different positions. 
    
    
    
    
     
   
   
   
   

 
Author
xudyh
 
Source
2015 Multi-University Training Contest 9
 

/* ***********************************************
Author        :CKboss
Created Time  :2015 08 19      21 58 12 
File Name     :HDOJ5396.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;

typedef long long int LL;

const int maxn=210;
const LL mod=1e9+7LL;

int n;
LL a[maxn];
char ope[maxn],cmd[maxn];
LL dp[maxn][maxn];
LL C[maxn][maxn];
LL jc[maxn];

void init()
{
	jc[0]=1; C[0][0]=1LL;
	for(int i=1;i<maxn;i++) 
	{
		C[i][i]=C[i][0]=1LL;
		jc[i]=(jc[i-1]*i)%mod;
	}
	for(int i=1;i<maxn;i++)
	{
		for(int j=1;j<i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
}

void DP()
{
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i]=a[i];
	for(int len=2;len<=n;len++)
	{
		for(int i=1;i+len-1<=n;i++)
		{
			int j=i+len-1;
			for(int k=i;k<j;k++)
			{
				int left=k-i;
				int right=len-2-left;
				LL t=0;
				if(ope[k]=='*')
				{
					t=(dp[i][k]*dp[k+1][j])%mod;
				}
				else if(ope[k]=='+')
				{
					t=(dp[i][k]*jc[right]%mod+dp[k+1][j]*jc[left]%mod)%mod;
				}
				else if(ope[k]=='-')
				{
					t=(dp[i][k]*jc[right]%mod-dp[k+1][j]*jc[left]%mod+mod)%mod;
				}
				dp[i][j]=(dp[i][j]+t*C[len-2][left]%mod)%mod;
			}
		}
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);

	init();
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%lld",a+i);
		scanf("%s",cmd+1);
		for(int i=1;i<n;i++) ope[i]=cmd[i];
		DP();
		printf("%lld
",dp[1][n]%mod);
	}
    
    return 0;
}