English

Indonesian

Pada suatu hari di kutub utara, ada suatu pabrik besar yang memproduksi mainan-mainan yang keren. Santa Claus, pemilik dari pabrik tersebut ingin mengirimkan mainan-mainan ini sebagai hadiah kepada banyak anak-anak yang menginginkan hadiah di hari natal menggunakan rusa terbang, karena setiap tahunnya jumlah mainan yang diproduksi meningkat dan rusa tgerbangnya semakin tua, ia ingin barang bawaannya seringan mungkin.

Berungtung pada natal kali ini (Desember 2014) ia berhasil menciptakan teknologi yang dapat menyimpan mainan dengan jumlah tanpa batas, ia menamakan ciptaannya itu "Kotak Ajaib", jadi setiap mainan dalam kotak ajaib tidak akan memiliki berat, sungguh hebat! Ia menciptakan kotak ajaib pada tanggal 23 Desember 2014, ada sisa 2 hari lagi menjelang natal, jadi ia ingin mempercepat proses pemasukan barangnya.

Ada banyak mainan yang harus dimasukkan dalam waktu singkat dan kotak ajaib tidak dapat menghisap banyak mainan dalam waktu singkat, jadi ia memutuskan untuk memasukkan mainan ke dalam beberapa kotak ajaib secara bersamaan. Misalkan jika mainan diberi nomor dari 1 hingga n, maka salah satu kemungkinannya adalah kotak ajaib pertama diisi mainan ke_2 hingga mainan ke_5, ... , kotak ajaib terakhir diisi mainan ke_n-7 hingga mainan ke_n-1. Perhatikan bahwa ada kemungkinan kotak ajaibnya Santa tidak dapat menghisap semua mainan di pabriknya dengan tepat waktu meskipun ia menggunakan beberapa kotak ajaib secara bersamaan, jadi beberapa mainan mungkin tertinggal di pabrik untuk natal berikutnya.

Karena kotak ajaib masih dalam "versi percobaan", kemampuan kotak ajaibnya belum sempurna dan masih terdapat beberapa kekurangan dalam fungsinya, salah satu kekurangan yang paling parah adalah kotaknya hanya bisa menghisap mainan yang berurutan saja, misalnya jika mainan nomor 3 dan nomor 5 dimasukkan kedalam kotak ajaib yang sama, mainan nomor 4 mau tidak mau pasti juga akan terhisap ke dalam kotak itu. Karena masalahnya menjadi terlalu rumit, maka Santa ingin beristirahat dan meninggalkan pabriknya sejenak untuk memberi makan dan memberitahu rusa terbangnya kabar gembira bahwa ia berhasil menciptakan kotak ajaib sahingga rusa terbangnya tidak perlu mengangkut beban yang berat lagi seperti tahun lalu. Ia juga merencanakan bagaimana urutan pemasukkan mainan ke dalam kotak ajaib. Karena Santa ingin segalanya sempurna, maka ia ingin agar setiap kotak ajaib jika digunakan berisi setidaknya d mainan.

Sekarang ia penasaran ada berapa banyak cara ia dapat memasukkan mainan ke dalam kotak ajaibnya jika jumlah kotak ajaib sama dengan jumlah mainan di pabriknya. Tidak selalu semua kotak ajaibnya digunakan, ia hanya ingin menggunakan setidaknya satu kotak ajaib. Dapatkah anda membatunya menghitung berapa banyak cara ia dapat melakukannya?

Format Masukan

Pada baris pernama, terdapat satu bilangan bulat c yang melambangkan jenis berkas masukan. Untuk lebih jelasnya tentang jenis berkas, lihat bagian "Batasan".

Setiap baris berikutnya hingga EOF (end of line = akhir dari berkas masukan), terdapat 3 bilangan butat d, n, dan m

• d = Jumlah minimal mainan yang ingin dimasukkan Santa ke dalam setiap kotak ajaib.
• n = Jumlah mainan yang tersedia di pabriknya Santa.
• m = Modulo, kerena banyaknya cara bisa sangat-sangat besar, Santa pasti mengerti, ia hanya ingin banyaknya cara dimodulo m.

Format Keluaran

Untuk setiap jawaban yang didapatkan, keluarkan dua bilangan bulat d dan banyaknya cara dimodulo m dalam satu baris dipisahkan oleh satu spasi.

Batasan

2014 kasus uji.

1 ≤ c ≤ 3

1 ≤ d ≤ 2014 (d akan selalu unik di setiap berkas masukan, tidak ada dua kasus uji dengan d yang sama)

1 ≤ m ≤ 109

Jenis1: 0 ≤ n < 2×d; Nilai = 1 usntuk setiap jawaban yang benar.

Jenis2: 0 ≤ n ≤ maks(d2,2×d); Nilai = 10 untuk setiap jawaban yang benar.

Jenis3: 0 ≤ n < 264; Nilai = 100 untuk setiap jawaban yang benar.

Penilaian

Nilai akhir anda adalah jumlah nilai dari berkas jenis1 sampai jenis3.

Jika anda mencetak semua jawaban benar pada berkas masukan jenis 3,

anda akan mendapatkan nilai tambahan sebesar:

jika x=(25.0-[waktu eksekusi pada berkas 3])*8056.0

maka nilai bonusnya adalah bilangan bulat terbesar yang ≤ x

Contoh 1

Masukan:

1

1 1 1000

2 3 1000

3 5 1000

4 7 1000

Keluaran:

1 1

2 3

3 6

4 10

Nilai:

Karena ini adalah berkas masukan jenis 1, jadi setiap jawaban benar bernilai 1 poin

Untuk contoh ini nilai=4*1=4.

Contoh 2

Masukan:

2

1 2 1000

2 4 1000

3 6 1000

4 8 1000

Keluaran:

1 4

4 16

2 7

Nilai:

Perhatikan bahwa anda dapat mencetak jawaban dengan urutan bebas,

Karena ada 3 jawaban benar dan ini adalah masukan jenis 2 (setiap kasus uji bernilai 10 poin),

untuk contoh ini nilai=3*10=30.

Contoh 3

Masukan:

2

1 2 1000

2 4 1000

3 6 1000

4 8 1000

Keluaran:

1 4

3 10

4 16

2 7

Nilai:

Untuk contoh ini anda akan mendapatkan WA="Wrong Answer".

Ini terjadi karena untuk d=3 dan n=6 dan m=1000 jawaban yang bernar adalah 11,

tetapi yang dicetak adalah 10.

Lebih baik tidak mencetak "3 10" seperti di contoh 2 daripada mencetaknya tetapi salah.

Untuk kasus ini nilai = Tidak ada.

Contoh 4

Masukan:

3

1 11 1000

2 11 1000

Keluaran:

Nilai:

Karena tidak mencetak apa-apa maka nilai=0.

Hati-hati, anda akan mendapatkan WA jika jumlah nilai dari masukan jenis 1 sampai jenis 3=0.

Contoh 5

Masukan:

3

1 12345678987654321 1000

2 11 1000

Keluaran:

2 23

Nilai:

Karena ini adalah berkas masukan jenis 3, jadi setiap jawaban benar bernilai 100 poin

Untuk contoh ini nilai=1*100=100.

Contoh 6

Masukan:

3

1 3 5

2 4 6

Keluaran:

1 2

2 1

1 2

Nilai:

Semua jawabannya benar, tetapi karena d harus unik,

maka untuk contoh ini anda akan mendapatkan WA.

Nilai untuk kasus ini = Tidak ada

Contoh 7

Masukan:

3

1 3 1000000000

2 4 1000000000

Keluaran:

1 12

2 7

Nilai:

200

Penjelasan untuk "Contoh 7"

Ini semua 12 cara untuk memasukkan 3 mainan ke dalam satu atau lebih kotak ajaib dan setiap kotak ajaib setidaknya berisi 1 mainan.

Ini semua 7 cara untuk memasukkan 4 mainan ke dalam satu atau lebih kotak ajaib dan setiap kotak ajaib setidaknya berisi 2 mainan.

Informasi Tambahan

Semua masukan (n and m) dibangkitkan dengan distribusi acak merata dalam interval batasan.

Nilai saya saat publikasi dari soal ini adalah 66554, apakah anda bisa mengalahkan nilai ini(?)

Kabar baru: [2014-12-24 13:42:56] Selamat kepada Min_25, orang pertama yang menyalip nilai saya di soal ini.

Jika ada pengguna yang mendapatkan nilai sempurna (223554) saya tidak akan meningkatkan batasan atau mengubah berkas masukan, saya akan mengganti sistem penilaian (memperhitungkan waktu eksekusi program ke dalam penilaian), namun... apakah itu akan terjadi?

Kabar baru: Itu terjadi! [2015-01-02 22:38:52] Selamat kepada Min_25!

---

Lihat juga: Soal-soal pemrograman lainnya yang ditambahkan oleh Tjandra Satria Gunawan