题目描述

给定 n 个数字串，进行 k 次操作，每次操作在所有数位中任选两个不同位置交换，允许两次操作选择的位置完全相同。求 k 次操作之后，对于所有可能的操作序列，最终数字串乘积的和，结果对 $10^9+7$ 取模。

输入格式

第一行两个整数 n,k，表示数字串个数和操作次数。

接下来 n 行，每行一个数字串。

输出格式

一行一个整数，表示数字串乘积和对 $10^9+7$ 取模的结果。

样例

样例输入

2 2
12
3

样例输出

363

样例解释

第一次操作后有三种情况：{21,3} {32,1} {13,2}

第二次操作后有九种情况：{12,3} {31,2} {23,1} {23,1} {12,3} {31,2} {31,2} {23,1} {12,3}

答案为：$12\times 3+31\times 2+23\times 1+23\times 1+12\times 3+31\times 2+31\times 2+23\times 1+12\times 3=363$

数据范围：

对于 10% 的数据，$1\leq n\leq 5,1\leq k\leq 3,1\leq$单串长度$\leq 5$

对于另外 15% 的数据，$n=1$

对于另外 15% 的数据，$k=1$

对于 100% 的数据，$1\leq n\leq 100,1\leq k\leq 10^9,1\leq$串长总和$\leq 10^7$