给定长度为 $n$ 正整数序列 $A$，$B$。

在 $1$ 到 $n$ 选出至多 $k$ 个数，记作集合 $S$，剩下的数记作集合 $T$。

求:

$\sum_{S,T的所有不同情况}\prod_{x\in S}A_x\times\prod_{y\in T}A_y$

求 $O(n)$ 左右的解法。