eolymp
bolt
Try our new interface for solving problems
Məsələlər

"Same quantity, sum and product"

"Same quantity, sum and product"

Zaman məhdudiyyəti 4 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Your task is to write a program, which will count how many different multisets has N elements with sum S and product P (1N2^{5 }= 32, 1S2^{15 }= 32768 and 1P2^{36 }= 68719476736).

Two multisets are considered different when they differ by elements or by quantities of some elements. If two sequences differ by elements’ order only, they are the same multiset.

Giriş verilənləri

Input contains three space-separated integers N, S and P in the same line.

1N2^5=32, 1S2^15=32768 and 1P2^36=68719476736.

Çıxış verilənləri

Output exactly one integer number — the quantity of different multisets.

Nümunə

Giriş verilənləri #1
9 45 362880
Çıxış verilənləri #1
12

Qeyd

The 12 multisets for 1^st test case are:

1 2 3 4 5 6 7 8 9

1 2 3 4 6 6 6 7 10

1 2 4 4 4 5 7 9 9

1 3 3 3 4 6 7 8 10

1 3 3 4 4 4 7 9 10

1 3 3 4 4 5 6 7 12

2 2 2 3 4 6 7 9 10

2 2 2 3 5 6 6 7 12

2 2 3 3 3 5 7 8 12

2 2 3 3 4 5 6 6 14

2 3 3 3 3 4 5 8 14

2 3 3 3 4 4 4 7 15

Müəllif Ilya Porublev
Mənbə ACM-ICPC Ukraine 2013, 2nd Stage Ukraine, September 10-12, 2013