出题人太菜，暂无测试数据。

题目描述

幻想乡是一个被博丽大结界和虚幻与现实的境界所包围起来的一个美妙的地方。这里人和其他生物，例如妖怪、妖精等核平共处。

射命丸文（Syameimaru Aya）是一只鸦天狗，拥有操纵风的能力，已经活了千岁以上，是《文文。新闻》的主编，拥有着一本叫做《文花帖》的手账，记录幻想乡各地的大新闻。她不仅是天狗中速度最快的鸦天狗，思考能力非常强，以别人的几倍的思考速度思考，也拥有幻想乡最高等级的力量。

有一天，射命丸文在幻想乡中的某个角落找到了灵梦的符纸，她感到很惊讶，于是她将其拍摄了下来，她发现灵梦的符纸排列样子刚好组成了一个 \(n\) 行 \(m\) 列的矩形，且每个符纸上都有一个数字 \(a_{i, j}\)，如果将一个处于 \(i\) 行 \(j\) 列的符纸表示为 \(a_{i, j}(1 \leq i \leq n, 1 \leq j \leq n)\)，那么存在规律 \(a_{i, j} = a_{i - 1, j} + a_{i, j - 1}\)，且符纸边缘上的数都是 \(0\)（即对于任意 \(i\)，\(a_{i, 0} = 0, a_{0, i} = 0\)）。

现在，射命丸文想知道，依照顺序，第 \(n\) 行 \(m\) 列的符纸上的数应该是多少？

输入输出格式

输入格式

第一行两个正整数 \(n, m\)。
第二行 \(m\) 个整数，表示 \(a_{1, 0}\)。

输出格式

输出 \(a_{n, m}\)

样例

输入

3 5
1 2 3 4 5

输出

25

数据范围

对于 \(10 \%\) 的数据，\(1 \leq n, m \leq 100\)；

对于 \(50 \%\) 的数据，\(1 \leq n, m \leq 10^5\)；

对于 \(100 \%\) 的数据，\(1 \leq n, m \leq 10^7\)。