3438. 棋盘上的車

给定一张形如条形图的国际象棋棋盘，这张棋盘由 $n$ 条高度可能不相等的列组成，但保证所有列的底边都是处于同一水平线上的。如图：

现在需要在棋盘上挑选 $k$ 个格子放置彼此不攻击的车，请问有多少种方法？输出方案数模 ${10}^9+7$ 的余数。所谓不攻击，就是说任意两只车不能通过棋盘上连续的一行或一列格子直接连在一起。如图中两个 $b$ 是可以相互攻击的，应避免这样放置；但两个 $a$ 是攻击不到的，因为中间一段越出了棋盘的边界。