import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintStream; import java.util.Arrays; import java.util.TreeSet; /** * Solution to Prefix Free Code * * @author vanb */ public class prefix_vanb { private static BufferedReader br; private static PrintStream ps; /** The Modulo for the final answer */ private static final int MOD = 1000000007; /** A counter for index numbers */ private int nextindex = 0; /** * This is a node of a Word Tree. * A Word Tree is a tree where every node represents a letter (except the root), * and a child of a node represents that that letter comes after the given letter in some word. * * Suppose we've seen the words "cat" and "car" and "cur". The word tree would look like this: * * + * | * c * / \ * a u * / \ | * t r r * * @author vanb */ private class Node { // Index will be -1 for internal nodes. // For leaf nodes, it'll be the index of the initial string in the sorted array. public int index = -1; // The child links are the 26 letters of the alphabet. public Node children[] = new Node[26]; /** * Create a Node. * No parameters, we'll fill in the details later. */ public Node() { Arrays.fill( children, null ); } /** * Compute index numbers by traversing the tree. */ public void traverse() { boolean kids = false; for( Node child : children ) if( child!=null ) { child.traverse(); kids = true; } /** No kids? Then this is a leaf, and must be the next initial string. */ if( !kids ) index = nextindex++; } } /** * Fenwick Tree! * * A Fenwick Tree is a data structure that efficiently keeps a list of numbers, with two operations: * adjust: Change one of the numbers * sum: Add up all of the numbers up to a given point. * Both operations are O(logn). Isn't that cool? * * @author vanb */ private class Fenwick { /** The tree */ private int tree[]; /** * Create a Fenwick tree. * * @param size The size of your list */ public Fenwick( int size ) { tree = new int[size+1]; reset(); } /** * Start from scratch. */ public void reset() { Arrays.fill( tree, 0 ); } /** * Add a delta to list[i]. * * @param i Index * @param diff Value change */ public void adjust( int i, int diff ) { for( ; i0; i -= (i&-i) ) { result += tree[i]; } return result; } } /** * Do it! */ private void doit() throws Exception { String tokens[] = br.readLine().trim().split( "\\s+" ); int n = Integer.parseInt( tokens[0] ); int k = Integer.parseInt( tokens[1] ); // Read the initial strings String initials[] = new String[n]; for( int i=0; i=0 ) { // Record the "digit" digit[j++] = (index - fenwick.sum( index+1 ) ); // We've seen this index, add it to the Fenwick Tree fenwick.adjust( index+1, 1 ); // Start back at the root node = root; } } // Now, convert those "digits" into an answer. long answer = 1L; long multiplier = 1L; j = n-k+1; for( int i=k-1; i>=0; i-- ) { answer += multiplier * digit[i]; answer %= MOD; multiplier *= j++; multiplier %= MOD; } ps.println( answer ); } /** * main * * @param args * @throws Exception */ public static void main( String[] args ) throws Exception { br = new BufferedReader( new InputStreamReader( System.in ) ); ps = System.out; new prefix_vanb().doit(); } }