题目描述

南宋数学家秦九韶提出了一种高效计算多项式值的算法，称为"秦九韶算法"。该算法通过将多项式层层嵌套，将计算次数从朴素算法的 O(n²) 降低到 O(n)。

给定多项式 f(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀，秦九韶算法将其转换为嵌套形式： f(x) = aₙx + aₙ₋₁ 然后乘以 x 再加 aₙ₋₂ 再乘以 x 再加 aₙ₋₃ ... 最后乘以 x 再加 a₀

现在，请你实现该算法，计算给定多项式在 x = x₀ 处的值。

输入格式

• 第一行：一个整数 n，表示多项式的最高次数
• 第二行：n + 1 个整数，依次表示 a₀, a₁, ..., aₙ（从低次到高次）
• 第三行：一个整数 x，表示自变量的值

输出格式

• 一个整数，表示多项式在 x 处的值 f(x)

样例输入

2
1 2 3
2

样例输出

17

样例解释

多项式为 f(x) = 3x² + 2x + 1
当 x = 2 时，f(2) = 3×4 + 2×2 + 1 = 12 + 4 + 1 = 17

使用秦九韶算法计算过程：

1. 初始值 = 3 (最高次项系数)
2. 3×2 + 2 = 8
3. 8×2 + 1 = 17

数据范围

• 0 ≤ n ≤ 1000
• -10000 ≤ aᵢ, x ≤ 10000
• 保证结果在 int 范围内