小白逛街

Grade 0 Open Time Thursday, 21 February 2013, 11:02 pm
Discount 0.8 Time Discount Thursday, 28 February 2013, 11:02 pm
Allow late Yes Close Time Thursday, 28 February 2013, 11:02 pm
Input file white.in Output file white.out
【背景】
    小白在一个由n条横街,m条纵街的地方逛街。现在他饿了,想去买小吃。已知小吃街在第n条横街上,且每个街区有ai家小吃店。小白站在这个地方的左上角,为了早点买到小吃,他只向下和向右走。
【问题描述】
    在这n*m的地方,从左上角,只向下和向右走到第n行的某一段的ai中任意一点,求有多少种不同的方案。同一家店不同路线 和 同一路线不同店均视为不同的方案。
【输入文件】
第一行有二个整数n,m表示n行m列。
接下来m-1行,每行一个数ai表示第n行的每个街区的小吃店数量。
【输出文件】
方案总数。
 
【输入样例】
 
4 5
2
1
0
1
 
【输出样例】
26

小白

       
       
       

  2       1      0     1

26= 2*1 + 1*4 + 0*10 + 1*20
【数据范围】
对于 30%数据, 0<=n,m<=10;ai=1
对于100%数据, 0<=n,m<=1,000
对于 100%数据,0<=ai<=1000