|
||||||||||
String ModTime Limit: 11000/5500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 364 Accepted Submission(s): 135 Problem Description There are strings of length $L$ consisting of the first $k$ $(2\le k\le 26)$ lowercase letters.The total number of strings is $k^L$. For each pair$(i,j)$($\ 0\leq i,j\leq n-1\ $),please count the number of strings which contain $p$ lowercase letters 'a' and $q$ lowercase letters 'b', satisfying $p \equiv i\ (mod\ n) $ and $ q \equiv j\ (mod\ n) $ . Print the matrix $A$,$A[i][j]$ is the answer of pair$(i,j)$. Input The first line contains an integer $T(T \le 10)$. Then $T$ test cases follow. For each test case the first line contains three integers $k(2\le k\le 26)$,$L(1\le L\le 10 ^{18})$,$n(1\le n\le 500)$. $\sum n\le 2000$. Output For each test case, output $n$ lines contain $n$ integers. which is the answer modulo $P=10^9+9$,satisfying $n|(P-1)$. Sample Input
Sample Output
Source | ||||||||||
|