import java.io.*; import java.util.*; import java.math.*; /** * Solution to Cheats * * @author vanb */ public class cheats_vanb { public Scanner sc; public PrintStream ps; /** The two main parameters */ public int n, k; /** Some helpful constants */ public static final long MOD = 1000000007L; public static BigInteger BIGMOD = new BigInteger( ""+MOD ); /** We'll compute the factorials once and store them. */ public long fact[] = new long[201]; /** The number of childen of each node */ public int nkids[] = new int[200]; /** The size of each node's subtree */ public int subnodes[] = new int[200]; /** A list of the children of each node */ public int kids[][] = new int[200][200]; /** * ways[n][0][k] is the number of ways of arranging the * subtree rooted at node n, using exactly k cheats, * but not using a cheat to skip node n. * * ways[n][1][k] is the number of ways of arranging the * subtree rooted at node n, using exactly k cheats, * but using a cheat to skip node n. */ public long ways[][][] = new long[200][2][201]; /** * In the spirit of cheating, we'll use Java's BigInteger * to get the mod inverse. * * @param x A number * @return The inverse of x, mod MOD. */ public long modinv( long x ) { BigInteger bigx = new BigInteger( ""+x ); return bigx.modInverse( BIGMOD ).longValue(); } /** * A memoization array to help us compute the total number of * ways to arrange all of the childen of a node. * * products[nk][cheats] is the number of ways to arrange * the last nk kids of this node, using 'cheats' cheats. * Node that this is just the product of the number of * ways of arranging each node, and does not take into account * mixing the sublists of the kids. */ public long products[][] = new long[201][201]; /** * Compute the number of ways to arrange the kids of a node. * * @param node The node in question * @param nkids The number of kids we're considering * @param skip A node to skip using a cheat * @param using The number of cheats to use * @return The number of ways to arrange the last 'nkids' kids of a node */ public long compute( int node, int nkids, int skip, int using ) { if( products[nkids][using]<0L ) { long result = using==0 ? 1L : 0L; if( nkids>0 ) { result = 0L; int kid = kids[node][nkids-1]; for( int i=0; i<=using; i++ ) { result += ((ways[kid][0][i]+(kid==skip?0L:ways[kid][1][i])) * compute( node, nkids-1, skip, using-i )) % MOD; result %= MOD; } } products[nkids][using] = result; } return products[nkids][using]; } /** * Count the total number of ways to achieve the objectives in a subtree * rooted at a node. * * @param node Root */ public void countWays( int node ) { int nk = nkids[node]; if( nk==0 ) { // Only one way to handle a leaf. // No cheating possible. ways[node][0][0] = 1L; ways[node][1][0] = 0L; } else { // Denom is the denominator of the Combinations long denom = 1L; // Handle kids for( int i=0; i0; c-- ) { // We've got to change 'orders', since 'c' // nodes are no longer following 'node' o *= c; o %= MOD; o *= modinv( num ); o %= MOD; ways[node][1][i] += o*products[nk][i-1] % MOD; ways[node][1][i] %= MOD; // --num, with MODs num = (num+MOD-1) % MOD; } } } } } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); //new File( "cheats.sample" ) ); ps = System.out; //new PrintStream( new FileOutputStream( "cheats.vanb" ) ); fact[0] = fact[1] = 1L; for( int i=2; i<=200; i++ ) { fact[i] = i*fact[i-1] % MOD; } for(;;) { n = sc.nextInt(); k = sc.nextInt(); if( n==0 ) break; Arrays.fill( nkids, 0 ); Arrays.fill( subnodes, 0 ); Arrays.fill( ways[0][0], 0 ); Arrays.fill( ways[0][1], 0 ); for( int i=1; i