public class Solution {
    int counter=0;
    public int NumRollsToTarget(int d, int f, int target) {


        return helper(d,f,target,new Dictionary<string,int>());
    }

    int helper(int d, int f, int target,Dictionary<string,int> map)
    {
        if (d==1 && f>=target && target>=1)
            return 1;

        if (d==0 || target==0)
            return 0;

        string key=d+"_"+target;
        if (map.ContainsKey(key))
            return map[key];


        int val=0;
        for(int i=1;i<=f;i++)
        {
            val+=helper(d-1,f,target-i,map);
            val=val%(1000000000+7);

        }
        map.Add(key,val);
        return map[key];
    }
}