Amoeba and Xiaoqiang are good friends.
Amoeba and Xiaoqiang are by the sea, watching the waves. It is Xiaoqiang's first time facing such surging tides, and he is shouting with excitement. Amoeba, however, is very calm, recalling the days gone by—the ups and downs of his career, the setbacks in his emotions... In short, compared to the storms he has experienced in the past, today's waves are nothing at all.
Consequently, the two friends inevitably have a disagreement. To prove his point, Xiaoqiang builds a model. He abstracts the sea surface into a permutation $P[1 \dots N]$ of $1$ to $N$. He defines the wave intensity as the sum of the absolute differences of adjacent terms, that is: $$L = |P_2 - P_1| + |P_3 - P_2| + \dots + |P_N - P_{N-1}|$$
Given $N$ and $M$, what is the probability that a randomly chosen permutation of $1 \dots N$ has a wave intensity not less than $M$?
Please output the answer rounded to $K$ decimal places.
Input
The first line contains three integers $N$, $M$, and $K$, representing the length of the permutation, the wave intensity, and the number of decimal places to output, respectively.
Output
A real number rounded to $K$ decimal places.
Constraints
- For 30% of the data, $N \le 10$.
- For another 30% of the data, $K \le 3$.
- For another 30% of the data, $K \le 8$.
- For another 10% of the data, $N \le 50$.
- For 100% of the data, $N \le 100$, $K \le 30$, $0 \le M \le 2147483647$.
Examples
Input 1
3 3 3
Output 1
0.667
Note
There are 6 permutations of $N=3$: 123, 132, 213, 231, 312, 321; their wave intensities are 2, 3, 3, 3, 3, 2, respectively. Therefore, the probability that the wave intensity is not less than 3 is 4/6, which is 0.667.
You can also verify this probability using the following code:
int a[3]={0,1,2},s=0,n=3;
for (int i=0;i<1000000;i++){
random_shuffle(a,a+n);
int t=0;
for (int j=0;j<n-1;j++) t+=abs(a[j+1]-a[j]);
if (t>=3) s++;
}
printf("%.3f\n",s/1000000.0);