import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Mountain Scenes * * @author vanb */ public class scenes_vanb { public Scanner sc; public PrintStream ps; /** Modulus */ public static final long MOD = 1000000007L; /** Height of the frame */ public int height; /** * Memoization array: memo[n][m] is the number of ways * you can use a length of ribbon EXACTLY 'n' to make a scene * in a frame of width 'm'. */ public long memo[][]; /** * How many ways can you use a length of ribbon EXACTLY 'n' to make a scene * in a frame of width 'm'? * * @param n Length of ribbon * @param m Width of frame * @return The number of ways, mod MOD */ public long ways( int n, int m ) { // We'll use -1 to flag that memo[n][m] hasn't been computed yet if( memo[n][m]<0 ) { if( n>m*height ) { // If there's more ribbon than room in the frame, // then there's no way to use EXACTLY n length of ribbon. memo[n][m] = 0L; } else if( n==0 || m==1 ) { // If there's only one column, then there's only one way to // use EXACTLY n length of ribbon. // Likewise, if the length of ribbon is 0, there's // only one way to do that. memo[n][m] = 1L; } else { long result = 0L; for( int i=0; i<=n; i++ ) { // Split the frame in half: use i length of ribbon // on one side, n-i on the other. result += (ways(i,m/2) * ways(n-i,m-m/2)) % MOD; result %= MOD; } memo[n][m] = result; } } return memo[n][m]; } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; int length = sc.nextInt(); int width = sc.nextInt(); height = sc.nextInt(); // Create the memoization array memo = new long[length+1][width+1]; for( int i=0; i<=length; i++ ) { Arrays.fill( memo[i], -1L ); } // Go through all possible length of ribbon. You can't use // more than there's room for in the frame. long result = 0L; int maxusable = Math.min( length, height*width ); for( int i=0; i<=maxusable; i++ ) { result += ways( i, width ); result %= MOD; } // This is the number of scenes that are of all even height. // They're plain scenes, not mountain scenes. // Add 1 for the 0 case. long plains = Math.min( height, length/width ) + 1L; // Subtract the plains from the total number of scenes, // and be careful about the MOD. result = (result + MOD - plains) % MOD; ps.println( result ); } /** * @param args */ public static void main( String[] args ) throws Exception { new scenes_vanb().doit(); } }